Duckpin锦标赛

Time Limit:3000MS Memory Limit:65536K
Total Submit:0 Accepted:0

Description

In a Duckpin Tournament, the winner is decided by the player with the highest number of tournament points earned by playing a number of matches. Points are awarded for winning a match and scoring the highest game during the match. A duckpin match consists of a series of three lines, or games. The match winner is the player with the highest series score, i.e., three game total. The high game winner is the player with the highest score for a single line during the match.

A line of duckpins is divided into ten frames. In each frame a player has three tries to knock down ten duckpins with a ball. If the player knocks down all ten pins on the first try, a strike is awarded and the frame is concluded (see exception below). If the player knocks down all ten pins in two tries, a spare is awarded and the frame is concluded (see exception below). If during any of the three tries a foul is committed by the player crossing the foul line, the frame is concluded and only the pins knocked down prior to that try are counted for the frame. The points earned in a frame equal the number of pins knocked down plus any bonus points earned for a spare or a strike. The bonus points earned for a spare or strike equal the number of pins knocked down on the next try following a spare or on the next two tries following a strike. A foul following a spare or strike earns zero bonus points unless the foul occurs on the second try following a strike; then only the bonus points earned on the first try are counted. A spare or a strike normally concludes the frame. However, if a spare or a strike occurs in the tenth frame, the frame is concluded by the player immediately taking the appropriate number of tries to earn the bonus points. The score for each frame equals the number of points awarded for the frame plus the score in the previous frame.

Write a program to produce a scoring summary for one or more duckpin matches of one to four players.

Input

The input for each match consists of an integer indicating the number of players, a list of players’ names (each name is a max. length of 10 alpha characters), followed by lines of integers representing the number of pins knocked down by each player on the first, second, or third try in each game in the match. The match is concluded by ‘#’. The input is concluded when the number of players for a match is zero.

Since each match consists of three games and each player gets three tries per frame in each game, the total number of lines of integers in the match will be nine times the number of players. The players play in the order that the names were listed. The order of the lines is: (1) three lines for the first player in the first game followed by three lines for each of the other players for the first game, (2) three lines for the first player in the second game followed by three lines for each of the other players for the second game, (3) similarly for the third game with the match concluded by ‘#’. The line of integers representing the first try will have at least ten integers but no more than twelve. Since a second or third try may not be attempted in a frame, the second and third lines may have less than ten integers. A negative integer indicates the number of pins knocked down however the player fouled on the try.

Output

The output shows a frame by frame score for each player for each game in the match. Each line of output consists of the player’s name, left justified in a field ten characters wide, and ten integers, right justified with a field four characters wide. At the end of the match report the match and high game winner followed by a blank line.

Sample Input

3
Tim Jim Bob
5 7 8 5 10 10 10 8 9 10 10 10 (scores for Tim’s first game)
5 2 1 4 1 0
0 1 1 1 1
10 10 9 8 9 9 10 9 9 9 8 (scores for Jim’s first game)
1 1 1 0 1 1 1
1 1
7 6 8 9 -10 8 9 8 10 10 8 1 (scores for Bob’s first game)
3 2 2 1 1 1 1
2 1 1
0 8 8 8 9 7 6 -6 7 9 (scores for the second game)
6 1 2 1 0 1 3 3 0
3 0 1 1 1 0 0
5 7 10 9 8 9 10 7 8 9 7
5 3 1 2 1 -3 2 1 (blank line shows no 3rd
tries were used in this game)
9 8 9 8 9 7 10 9 9 9
1 1 1 2 1 2 0 1 0
1 1 1 1
5 6 7 8 9 10 10 -10 10 10 10 10 (scores for the third game)
4 2 3 1 1
0 2 1
8 7 6 10 9 9 10 7 8 6
2 2 3 1 0 3 1 3
1 0 1 1 1
9 8 9 9 9 8 10 10 10 8
1 2 1 1 1 2 1
1
#
0

Sample Output

Tim 17 26 36 46 76 104 123 133 143 173
Jim 29 49 67 77 96 106 126 145 164 182
Bob 16 26 45 55 55 65 83 93 121 140
Tim 9 18 36 46 56 65 74 74 93 102
Jim 17 37 57 75 94 114 131 138 157 174
Bob 18 28 46 65 82 92 111 121 140 150
Tim 9 19 37 47 67 87 97 97 127 157
Jim 17 27 36 56 75 85 105 123 133 143
Bob 18 37 56 75 93 113 143 171 190 200
Jim has the high series score of 499.
Bob has the high game score of 200.

Hint

上面Sample Input中的括号和括号中的字符仅仅为了说明，在真正的测试数据中是没有的。

Source

调度问题

Time Limit:3000MS Memory Limit:65536K
Total Submit:1 Accepted:0

Description

A project can be divided into several parts. Each part should be completed continuously. This means if a part should take 3 days, we should use a continuous 3 days do complete it. There are four types of constrains among these parts which are FAS, FAF, SAF and SAS. A constrain between parts is FAS if the first one should finish after the second one started. FAF is finish after finish. SAF is start after finish, and SAS is start after start. Assume there are enough people involved in the projects, which means we can do any number of parts concurrently. You are to write a program to give a schedule of a given project, which has the shortest time.

Input

The input file consists a sequences of projects, with an empty line indicates the end of input.

Each project consists the following lines:

the count number of parts (one line)
times should be taken to complete these parts, each time occupies one line
a list of FAS, FAF, SAF or SAS and two part number indicates a constrain of the two parts
a line only contains a '#'hibar indicates the end of a project
Note: the number of parts will never be greater than 257

After last project is 0.

Output

Output should be a list of lines, each line includes a part number and the time it should start. Time should be a non-negative integer, and the start time of first part should be 0. If there is no answer for the problem, you should give a non-line output containing "impossible".

A blank line should appear following the output for each project.

Sample Input

3
2
3
4
SAF 1 2
FAF 2 3
#
3
1
1
1
SAF 1 2
SAF 2 3
SAF 3 1
#
0

Sample Output

Case 1:
1 4
2 1
3 0

Case 2:
impossible

Hint

题目类型：图论

Source

Machine Surfaces

Time Limit:3000MS Memory Limit:65536K
Total Submit:0 Accepted:0

Description

An imaging device furnishes digital images of two mechined surfaces that eventually will be assembled in contact with each other. The roughness of this final contact is to be estimated.

A digital image is composed of the two characters, "X" and " " (space). There are always 25 columns to an image, but the number of rows, N, is variable. Column one (1) will always have an "X" in in and will be part of the surface. The left surface can extend to the right from column (1) as contiguous X's.

Similarly, column 25 will always have an "X" in it and will be part of the right surface. The right surface can extend to the left from column 25 as contiguous X's.

Digital-Image View of Surfaces:

XXXX XXXXX
XXX XXXXXXX
XXXXX XXXX
XX XXXXXX
. .
. .
. .
XXXX XXXX
XXX XXXXXX

In each row of the image, there can be zero or more space characters separating the left surface from the right surface. There will never be more than a single blank region in any row.

Fro each image given, you are to determine the total "void" that will exist after the left surface has been brought into contact with the right surface. The "void" is the total count of the spaces that remains between the left and right surfaces after they have been brought into contact.

The two surfaces are brought into contact by displacing them strictly horizontally towards each other until a rightmost "X" of the left surface of some row is immediately to the left of the leftmost "X" of the right surface of that row. There is no rotation or twisting of there two surfaces as thay are brought into contact; they reamin rigid, and only move horizontally.

Note: The original image may show the two surfaces already in contact, in which case no displacement enters into the contact roughness estimation.

Input

The input consists of a series of digital images. Each imaga data set has the following format:

First line - A single unsigned integer, N, with value greater than zero (0) and less than 13. The first digit of N will be the first character on a line.

Next N lines - Each line has exactly 25 characters; one or more X's, then zero or more spaces, then one or more X's.

The end of data is signaled by a null data set having a zero on the first line of an image set and no furher data.

Output

For each image you receive as a data set, tou are to reply with the total void (count of spces remaining after the surfaces are bought into contact). Use the default output for a single integer on a line.

Sample Input

In the example input file below, the spaces have been replaced with the character "B" for ease of reading. The actual input file will use the ASCII-space character, not "B".

4
XXXXBBBBBBBBBBBBBBBBXXXXX
XXXBBBBBBBBBBBBBBBXXXXXXX
XXXXXBBBBBBBBBBBBBBBBXXXX
XXBBBBBBBBBBBBBBBBBXXXXXX
2
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
1
XXXXXXXXXXBBBBBBBBBBBBBXX
0

Sample Output

4
0
0

Source

没有人会吗?!不会吧