Problem A
Who Gets The Largest Piece?

Source file:

Input file: cake.in

Output file: cake.out

 

In the rectangle ABCD below, line segments ST and UV separate the rectangle into  three sections. One can think of ABCD as a cake and use a knife to cut it along the lines ST and UV. Here S, T, U, and V must be on the perimeter of ABCD. To know   which piece of cake is the largest, one can compute the area for each of these three    sections. You are to write a program to calculate the sizes of various shapes after two cuts separate ABCD. Display these three or four sizes in a descending order, i.e., the area of the largest section followed by the next largest, and so on. Each size must be printed exact to two digits to the right of the decimal point. Use your program to process N rectangles and select the largest section you find.

Input

The first line of the input file contains a positive integer N indicating the number of data sets to follow. Each of the following N lines contains the x and y coordinates of points A, B, C, D, S, T, U, and V respectively. These sixteen integers are separated by spaces.

Output

For each data set in the input file, output the areas of the separated sections in a descending order. Use spaces to separate these values. At the end, output the largest area from the N data sets in the last line.

Sample Input

2

0 4 16 4 0 0 16 0 4 4 8 0 15 4 10 0

-1 5 5 5 -1 0 5 0 0 5 0 0 -1 3 5 3

Sample Output

26.00 24.00 14.00

15.00 10.00 3.00 2.00

26.00

Remarks for review: The actual input data sets can include the following cuts with coordinates x and y ranging from negative integers to zeroes and positive integers.

 
Problem B
Road Map
Input file: pb.in

A road map is constructed from numbers of piecewise intervals. Each piecewise intervals is represented by two end points encompassed with parenthesis, e.g., ((100,250), (250,350)). Each point belongs to a point in the 2D plane with two integer axis values, i.e., x value and y value. Define the terminology FIRST SEE set means that, given a specific point, all the piecewise intervals which can be seen (more than two points of the piecewise intervals) by the point in all the directions. In other meaning, the FIRST SEE set defines the set of piecewise interval which are not blocked by other intervals with the standpoint of the point in the 3600 directions. Given a series of piecewise interval represents some specific city road map and a given specific point, write a program to find the FIRST SEE set of the point?

Input File

The input file contains a series of piecewise interval which represent some specific road map and finally a given specific point. Each line specifies the interval, the given point and ends with *.

Line 1: ((100,250),(250,350))

Line 2: ( (u,v),(s,t))

….

Line n: (p1,p2)

Line 1:n+1: * ……………………… end of input file

Output File:

The output file contains several lines. Each line represents a element of the FIRST SEE set of the given specific point(the set should by sorted in a increasing order with the sum of axis x value and axis y value of the first point of the intervals firstly, and the sum of the second point of the intervals secondly) Sample Input File:

((120,150),(180,300))

((150,450), (230,450))

((180,550),(200,460))

((100,100),((200,110))

((500,380),(550,250))

((100,100),((150,130))

(200,200)

*

Sample Output File:

((100,100),((150,130))

((100,100),((200,110))

((120,150),(180,300))

((150,450), (230,450))

((500,380),(550,250))

Problem C
Text Compression
Input file: pc.in

In this assignment we consider the problem of compressing a text string using a dictionary. The dictionary consists of (dictionary string, code word)-pairs, each representing the code word that can be used to replace a substring in the text. The code words are binary bit strings, not necessarily of equal length. The text compression problem is that of, given a text string over some finite alphabet and a dictionary, deciding the length of the shortest binary bit string which encodes the original text string.

Example 1.

text string : abcdef

Dictionary:

Dictionary 

string
a
abc
abcd
bcd
def
ef
Code word
01
0
1011
1
10
11
What follows are three different ways of encoding the text string:
Method 1
a
bcd
ef
01
1
11
Length of the compressed string (i.e., 01111) = 5
Method 2
abc
def
0
10
Length of the compressed string (i.e., 010) = 3
Method 3
abcd
ef
1011
11
Length of the compressed string (i.e., 101111) = 6

Clearly, Method 2 results in the shortest compressed string whose length is 3. Your job in this assignment is to find out the length of the shortest compressed string. If the text string cannot be compressed using the given dictionary, 0 should be returned. (For example, the text string abcxxx cannot be compressed using the dictionary in Example 1.)

The first line of the input file contains the text string to be compressed. Following this are (dictionary string, code word)-pairs, each of which occupies a line of the input file. (For the sake of simplicity, we assume that the text string is over the alphabet which consists of the 26 lower-case characters `a, b, c, …, z’. Examples of such text strings include: abcdef, thisisatextstring, and acmprogrammingcontest.

With respect to Example 1, the input and output files are the following

Input file:

abcdef

(a, 01)

(abc, 0)

(abcd, 1011)

(bcd, 1)

(def, 10)

(ef, 11)

Output file:

3

2

Problem D
Gambling

A cheating casino creates an electronic symbol-bar machine. This machine has 3 belts attached to 3 wheels. Symbols from A to y, are painted on each belt in alphabetic order. Figure 1 shows the display of this kind of machine. Totally there are 113 symbols printed on each belt. These symbols are orderly listed in Table 1. A belt will display the same symbols on the screen if a wheel rolls 113 steps. When the bar handle is pulled, each wheel will roll certain steps, according to three formulas. For example, if (6*N + 3) is the formula for the first wheel’s step-movement, where N is the Nth times the bar handle is pulled after the machine is reset, the first wheel will roll (6 * N + 3) steps and show another 3 symbols on the screen. Assume each wheel rolls on the same direction, from bottom to top according to Figure 1. Each wheel has different formula for directing how many steps to move its belt. The three formulas are specified as input data in this problem. Once 3 Js are displayed on the center row of the screen, it means a BINGO. One hundred times the bet will be rewarded to the gambler.

 

Figure 1: The display of the symbol-bar machine
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
a
b
c
d
e
f
g
h
i
j
k
l
m
n
p
q
r
s
t
u
v
x
a
b
c
d
e
f
g
h
i
j
k
l
n
o
y
u
v
x
z
A
B
E
F
G
L
J
K
H
M
O
Q
R
,
.
/
'
;
7
4
3
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
              
 
 
Table 1: The symbols printed on the belts
Now, a gambler enters into this casino and finds one Symbol-bar machine, which shows three symbols on the central line of the display. These three symbols are also specified as input data in this problem. This gambler wants to know how many times that he needs to pull the bar-handle to win a BINGO prize. Please write a program to help him. Further constraints and assumptions to this problem are specified as follows.
  1. The initial symbols displayed on the center row of the screen after the machine is reset are specified in the input file, too. For example, 12, 58 113 means the first 3 symbols showed on the center row of the screen are L, j, and y, after the machine is reset. The first value is used to show the initial symbol showed on the screen of the left wheel, while the second and third value are used to specify the symbols on the middle and right wheels.
  1. Following above input data are three formulas. The formulas are all in the (a * N + b) format, where N is the Nth times the bar handle is pulled after the machine is reset. The values of ‘a’ and ‘b’ are used as the input data. There are 6 values specified in the input file. The first two numbers are used for controlling the left wheel. The second two numbers are used for controlling the middle wheel, and the last two numbers are used for controlling the right wheel.
  2. Another following input data are 3 values used to specify the symbols showed in the screen at the time the gambler chooses that machine. This means after the machine was reset, there are people before the gambler chosen this machine and pulled the machine bar in certain times, which causes the machine to roll certain steps to show the current symbols on the screen. We assume it is the first time, after the machine was powered on, this pattern displayed on the screen when the gambler chooses this machine.
  3. The output data is a number to indicate how many times the bar-handle needs to be pulled by the gambler to win a BINGO.
  4. Instead of a number to show the number of times the bar-handle is pulled, if it is impossible for this gambler to win a BINGO, print "impossible".
  5. Each line of the input file is a configuration, which is nothing related to other lines. A ‘*’ in the last line of the input file represents the end of the input data.
Input File

The input file contains (K+1) lines. Each line specifies the input data for each test.

Line 1: W, X, Y, a, b, c, d, e, f, A, B, C

Line 2: P, Q, R, s, t, u, v, w, x, D, E, F

……

Line K: I, J, K, m, n, o, p, q, r, X, Y, Z

Line (K+1): * …………………………….. end of input file

Output File

The output file contains K lines. Each line is the output for each input configuration listed in input file.

Line 1: abcd ……………………………… a numerical number

Line 2: efgh ………………………………. a numerical number

….

Line K: wxyz ………………………………… a numerical number

Sample Input File

74 74 74 0 1 0 1 0 1 75 75 75

1 1 1 0 1 0 1 0 1 77 77 77

3 5 7 0 1 0 1 0 1 75 75 75

*

Sample Output File

112

110

impossible

Problem E
Expression Evaluation

Write a program that can understand and calculate the infix notation expressions. All the values given and to be evaluated are considered to be only integers. The possible symbols of the expression include integer values, arithmetic operators, special symbols, keywords, and variables.

The values are just ordinary integral literal strings. The arithmetic operators are ordinary binary operators including ‘+’, ‘-’, ‘*’, and ‘/’; The special symbols include the equal sign ‘=’, parentheses, ‘(‘ and ‘)’, and the question mark ‘?’. The possible variables are just single English alphabets ranging from ‘a’ to ‘z’; these variables are initialized as zeros at first.

Each input line contains an assignment expression with a variable on the left-hand side, following by the equal sign in the middle. The right-hand side of the assignment expression will be an ordinary integral expression (possibly contains several variables); the value of the expression shall be assigned to the variable for later evaluation. If the right hand side expression is a question mark, output the value of the left-hand side variable. Further, the possible keywords in the input file include ‘if’, ‘while’, and ‘end’ statements. The syntax and meaning of while statement is as follows:

while ( [exp] )

[assignment-statements]

end

Here the interpreter will evaluate the value of [exp], if the value of [exp] is not zero, then the [assignment-statements] will be repetitively evaluated until the value of [exp] equals to zero. The syntax and meaning of if statement is just like the while-statement except that the [assignment-statements] will be evaluated just once if the value of [exp] is not zero.

Note:

  1. The division operator is supposed to be the integer division. For example, 13 / 4 shall be just 3, instead of 3.25.
  2. For simplicity, no nested statement is allowed with ‘if’ and ‘while’ statements. That is, the only possible statements within these block statement are assignment statements.
Input File

Several lines of expression described above. A single `0' (zero) in the input line signifies the end of input.

Output File

For each question marked expression, output the corresponding value of the variable in a line. Output a single star `*' to signify the end of outputs.

Sample Input

x = 4

y = 3 * x - 2

y = ?

z = 5 + 2 * y

z = ?

x = 7 - y / 3

x = ?

while ( x )

z = 2 * z

end

z = ?

0

Sample Output

10

25

4

400

*

Problem F
Prime Polynomials

Let (F, +,l ) be a field, and F[x] be the set of all polynomials in x. That is, a polynomial is in if and only if  for every . If , then  is called the leading coefficient of , and we say that  has degree .

Let the field be , There are only two elements, 0 and 1, in . The addition in  is defined as: , , . The subtraction operation is the same as addition. That is , , . The multiplication in  is defined as: , , .

Let  and  be two polynomials in . The addition, subtraction, multiplication, and division of  and are defined similar to its corresponding operation of the ordinary polynomials, except that all operations should be computed in as defined above. For example, .

A polynomial  is  in  I, if there is no polynomials  and  in  with degree at least 1, satisfying . In this problem, you are going to write a program to find prime polynomials of degree 1 to degree , where is a positive integer.

Input File

The input file contains only one positive integer  You may assume that .

Output File

The output file should contain a set of prime polynomials in . For each degree , , list the prime polynomial  with smallest . The format of the output file is shown in the Sample Output section.

Sample Input

5

Sample Output

x^1+x^0

x^2+x^1+x^0

x^3+x^1+x^0

x^4+x^1+x^0

x^5+x^2+x^0

 
Problem H
Move Grid Puzzle
Input file: ph.in
Output file: ph.out

The following figure shows a 3x3 grid puzzle.
0
5
8
7
4
3
2
6
1
Formation of the grid puzzle :

  1. The dimension is always 3x3.
  2. ‘0’ is always in left top corner. ‘1’ is always in right bottom corner.
  3. The rest grid are numbers between 2 ~ 8

    4. Movement :

    ‘0’ stands for blank cell. You may move the number next to ‘0’ to blank cell.
    Then ‘0’ will occupy the cell that the number moves away.
    The cost of this movement is exactly the number moved.

    For example :
    0
    5
    8
    7
    4
    3
    <TD VALIGN=TOP WIDTH="3