課程名稱︰高等程式設計
課程性質︰選修
課程教師：劉邦鋒
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2013.06.18
考試時限（分鐘）：
試題 :
Advanced Computer Programming 2013
Final Examination
National Taiwan University
06/18/2013
NOTE: You need to finish the writing part before doing the programming part.
Writing Part:
(1) Polymorphism (10%)
˙ Describe the principle and purpose of polymorphism. Please use a
complete example in C++ to illustrate your points. (5%)
˙ Please describe the mechanisms in C++ that make polymorphism possible.
The key words include virtual functions, class hierarchy, and
pointers/references. (5%)
(2) Accessing Data Member (10%)
Describe the difference between private, protected, and public data
members in C++. You should focus on the purpose of these different
mechanisms, and how to achieve the purpose with these data access
methods. Please give a complete example for each of them in C++, and
illustrate your points.
(3) Template Programming (10%)
Describe the purpose of template programming. You should focus on the
template mechanism, and how the mechanism achieves the purpose. Please
give a complete example in C++ to illustrate your points.
(4) Operator Overloading (10%)
Describe the purpose of operator overloading. Give a complete example of
operator overloading in C++, and explain why operator overloading can
achieve these purposes.
(5) Dynamic Programming (10%)
˙ What are the three principles of dynamic programming? Please use an
example to illustrate these principles. (7%)
˙ What is the major difference between dynamic programming and exhaustive
search? (3%)
Programming Part:
(1) Scheduler (10%)
We want to schedule many courses into a classroom. Each course has a
starting time and an ending time. The classroom can be used at any time,
but it can only accommodate one course at a time. If two courses overlap
then we cannot select them both. Now please write a program that selects
as many courses as possible.
(1.1) Input
The first line of the input is the number of test cases T. Each test
case starts with a line consisting of the number of courses C. The
i-th of the following line has two integers, the starting time S_i
and the ending time E_i.
(1.2) Output
The output consists of T lines. The i-th line has the maximum number
of courses that can be selected in the i-th test case.
(1.3) Technical Specification
˙ 1 ≦ T ≦ 50
˙ 1 ≦ C ≦ 10^5
˙ 0 ≦ S_i, E_i ≦ 2^32 (32-bit unsigned integer)
(1.4) Sample Input
2
3
3 6
2 4
3 7
3
2 4
3 6
4 7
(1.5) Sample Output
1
2
(2) Lights Off (20%)
We want to play a game called "Turn the lights off". Now we have 16 lights
as a 4 by 4 array. Each light can be either on or off. Each light has a
switch. The switch is designed so that if we toggle a switch, the status
of this light, and the four neighboring lights will change their status.
By changing the status we mean if the light is on then it will become off,
and if it is off then it will become on. Note that if you toggle a switch
around the boundary or the corner, then the number of its neighboring
lights is 3 or 2, not 4. Now given the initial status of the lights,
please find the minimum number of switches one has to toggle in order to
turn off all the lights. There are two subtasks:
1. In the first subtask we ensure that we can use all of the switches.
Please refer to the description and the input format for more details.
(10%)
That is, the last four line of the test case will be:
....
....
....
....
2. In the second subtask some switches may be broken. What is the minimum
number of switches to toggle in order to turn off all lights? Note that
the lights are independent from the switches and all lights are
functional. For example, even if a switch is broken, its light will
still change status if the switch next to it is toggled. It is just
that in this subtask some switch cannot be used. (10%)
(2.1) Input
The first line of input is the number of test case T. Each test
case contains 8 lines, each line with four-character string. The
first four strings are the status of the lights as in the first
subtask. The next four strings are the status of the switch - a '.'
(character "dot") means off and an 'O' (letter O, not number) means
on. The last four lines of test case indicates if the switch is
broken - a dot '.' means that it works and an 'X' means that it is
broken.
(2.2) Output
For each test case output the minimum number of switches to toggle
in order to turn off all the lights. Print '-1' if it is impossible
to turn off all the lights.
(2.3) Technical Specification
˙ 1 ≦ T ≦ 50
(2.4) Sample Input
4
....
....
....
....
....
....
....
....
..OO
...O
....
....
....
....
....
....
....
....
....
....
XXXX
XXXX
XXXX
XXXX
..OO
...O
....
....
..XX
...X
....
....
(2.5) Sample Output
0
1
0
-1
(3) Builder (20%)
We want to build an L-shape house in an N by N grid. Every sides of the
house should align to the grid. Note that the width and length of this
house is a power of 2, and is at least 2. Some cells in this grid is not
suitable for building houses and should be avoided. Now please determine
the maximum size of the house that can be built, and the number of
possible placements on which we can build the largest houses. Note that
the house can be rotated in four different orientations, and it is
guaranteed that there will be at least one position that we can build the
house. The places for building the largest house can overlap.
For example, here are 4 size-2 L-shape houses in different directions:
OOOO OOOO OO OO
OOOO OOOO OO OO
OO OO OOOO OOOO
OO OO OOOO OOOO
There are two subtasks:
1. In the first subtask we ensure that in any 2 by 2 cells in the grid,
at least one of the cell is bad for construction. (6%)
2. The second subtask removes the condition given in subtask 1. The input
and output specification are same as those of the first subtask. (14%)
(3.1) Input
The first line of the input is the number of test cases T. The first
line of the test case has the size of the grid N, then followed by
N lines. Each of the N lines has a string indicating the status of
the grid. If the character in the string is a '.' then the cell is
good for construction. If the character is an 'X' then the cell is
bad.
(3.2) Output
Each test case should output two numbers in a line. The first number
is the size of the largest house one can build, and the second is
the number of placements that we can build this house.
(3.3) Technical Specification
˙ 1 ≦ T ≦ 10
˙ 2 ≦ N ≦ 500
(3.4) Sample Input
3
3
...
.X.
...
3
...
...
...
4
..XX
..XX
....
....
(3.5) Sample Output
2 4
2 16
4 1