le.

15

Output
For each completely specified binary tree in the input file, the level order t
raversal of that tree should be printed. If a tree is not completely specified
, i.e., some node in the tree is NOT given a value or a node is given a value
more than once, then the string ``not complete'' should be printed.
Sample Input
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
Sample Output
5 4 8 11 13 4 7 2 1
not complete
参考试题3:
写一个求任意边平面多边形面积的程序
要求是：输入边数，然后依次输入每个顶点的坐标
有可能输入的数值不能构成正则多边形，也即，边与边之间发生了交叉，比如，四个顶
点分别为（0，0），（1，1），（0，1），（1，0）这种情况，这时候，请打印出“imp
ossible"字样；如果多边形合法，则请输出该多边形的面积
要注意的情况是：凹多边形的正确处理
Sample Input
5

16

0 0
0 1
0.5 0.5
1 1
1 0
Sample Output
0.75
Sample Input
4
0 0
0 1
1 0
1 1
Sample Output
Impossible
保送生试题:
Problem D . Code the Tree
Source File: tree.cpp Time limited: 1 second
Input File: tree.in Output File:tree.out
A tree(ie:a connected graph without cycles) with vertices numbered by the inte
gers 1,2....,n is given. The "Prufer" code of such a tree is built as follows:
the leaf(a vertex that is incident to only one edge) with the minimal number i
s taken. This leaf, together with its incident edge is removed from the graph,
while the number of the vertex that was adjacent to the leaf is written down.

17

In the obtained graph, this procedure is repeated, until there is only one ve
rtex left(which, by the way, always has number n). The written down sequence o
f n - 1 numbers is called the Prufer code of the tree.

Your task is, given a tree, to compute its Prufer code. The tree is denoted by
a word of the language specified by the following grammar:

T::= (N S)
S::= ,T S | empty
N::= integer


That is, trees have parentheses around them, and a number denoting the identif
ier of the root vertex, followed by arbitrarily many(maybe none) subtrees sepa
rated by a single comma character. As an example, take a look at the tree in t
he figure below which is denoted in the first example.


Note that, according to the definition given above, the root of a tree may be
a leaf as well. It is only for the ease of denotation that we designate some v
ertex to be the root. Usually, what we are dealing here with is called an "unr
ooted tree".


Input:
There is only one line in the input, which specifies a tree as described above
. You may assume that 1 <= n <= 50.
Output:
Generate a single line containing the Prufer code of the tree. Separate number
s by a single space. Do not print any spaces at the end of the line.



Sample input and output
tree.in
(2,(6,(7)),(3),(5,(1),(4)),(8))
tree.out
5 2 5 2 6 2 8
2007 年复试上机真题：
Problem A. Old Bill
Input file: standard input
Output file: standard output
Among grandfather's papers a bill was found.
72 turkeys $_679_
The first and the last digits of the number that obviously represented the
total price of those turkeys are replaced here by blanks (denoted _), for
they are faded and are illegible. What are the two faded digits and what
was the price of one turkey?
We want to write a program that solves a general version of the above
problem.
N turkeys $_XYZ_
The total number of turkeys, N, is between 1 and 99, including both. The
total price originally consisted of five digits, but we can see only the
three digits in the middle. We assume that the first digit is nonzero, that
the price of one turkeys is an integer number of dollars, and that all the
turkeys cost the same price.

19

Given N, X, Y, and Z, write a program that guesses the two faded digits and
the original price. In case that there is more than one candidate for the
original price, the output should be the most expensive one. That is, the
program is to report the two faded digits and the maximum price per turkey
for the turkeys.

Input
The first line of the input file contains an integer N (0<N<100), which
represents the number of turkeys. In the following line, there are the