PersonalCorpus 版 (精华区)

Problem A: Moving Object Recognition
(input file: moving.in)

There are many scenarios in which we need to know how fast an object 
is moving. For example, the air-traffic controller in an airport would 
like to know the speed of a descending plane and give warning if it's 
too fast or too slow. The speed detection cameras have helped the police
 to catch the speeding drivers, and so on.
In this problem, you are supposed to write a program to recognize the 
speed of a moving object.
Assume that an object is moving on a two dimensional plane, with a 
constant speed and direction. A camera is taking a shot every second. 
Assume the camera can record the real situation of the plain - you don't
 need to worry about the view-angle.
The background is black and the only object is white, except some 
noise introduced by the camera. Anyway, you can assume that the 
largest continuous white area is always the object. There is always only
 one largest continuous white area in this problem. 
Given several pictures taken by the camera, calculate the speed of the 
object. Output the speed of the object.
A picture is represented by a matrix which contains “.” or “x” only,
 where"." in the matrix means a black block and "x" means a white block.
 There are at least two pictures.
Here are some detailed definitions:
l   The edge of each block is 1 mm (That is, each “.” or “x” in the 
matrix represents one 1mm*1mm block.) 
l   "The speed of the object" is defined by the moving speed of the center
 of the object as geometric center : . Anyway, all the objects are 
made of square blocks. The geometric center of a single square block 
is the center of the block. So the geometric center of the object can be
 calculated as: . Where (X[i],Y[i]) is the coordinates of the i-th box’
s center and N is the number of blocks in the object.
l   A white area is a set of white blocks.
l   A white area is called "continuous white area" if and only if there is
 always a path connecting two arbitrary blocks in this area. All the 
blocks in the path are within this area. And each pair of sequential 
blocks along this path shares a common edge.
l   The average speed is calculated as described in the physics textbook: 
  where t is over all the discrete observation time from 0 to T-1. In 
this problem, we define T as half of the number of observation points. 
(There are always even number observation points in the test suit.)  
is defined as the observed position of the object’s center in time t, 
that is,   calculated from the t-th image.
l   The positive direction of X axle is from the left to the right; the 
positive direction of Y axle is from the top to the bottom.

Note that you may get different shape of an object in different 
pictures. 
Input
The input is a file containing several data cases. Each case begins with
 a line, with only two numbers: m and k. Then follows by several m*k 
(m columns, k rows) matrices. Each matrix represents one picture taken 
by the camera. There are at least two pictures. There is always a 
separator line between each matrix inside a data set. The separator line
 is a line with m "-"s. The last matrix of a data set is followed by a 
terminating line - a line with m "="s.
A line with two zeros presents the end of the input file. 
The picture size is at most 256*256. There are at most 256 pictures in 
one test case.
Output
For each test case, output a line with two numbers which represent the 
speed of the object in X and Y direction respectively. The accuracy is 
up to 2 digits after decimal point. The speeds of the objects are in 
mm/s.
 

Sample input    Output for the sample input
10 5.........x.....xxx.x....xxx........xxx..x.........----------.......
..x.........x...xxx......xxx.....x..xxx....==========0 0    -2.00 1.00
 
Problem B: Random Walk
(input file: random.in)

Random Algorithms are very popular now. For example, it's widely used in
 cryptography (primality test and etc.).
Different from the normal definite algorithms, random algorithms may not
 have a definite running trace. Sometimes, it comes to some point, flips
 a coin, and decides where to go according to the result of the coin 
flipping.
The following command may be such a point:
x=random(1);      // random(1) returns a random number from [0..1) 
uniformly
IF x > 0.3 GOTO ...
When the random program comes here, it generates a random number and 
assigns it to x, if x is greater than 0.3 it goes to somewhere; 
otherwise, it goes straight ahead. So, the program goes somewhat like 
a drunk man walking a long the street. You can't predict where the 
program should go beforehand.
Your task in this problem is to create a simple Random Program 
Evaluator, which can calculate the expected running time of some 
random algorithms.
A simple random program is described as follows:
1.  There are several reserved words: "NOP", "IF", "GOTO", "END", "PROC",
 "PROG_START", and "PROG_END", case is sensitive. 
2.  A program starts with "PROG_START" and ends with "PROG_END".
3.  A program may have one or more procedures. 
4.  Each procedure starts with "PROC [name]". [name] is the name of 
this procedure. It can be any string that only contains characters or 
numbers, except reserved words.
5.  A procedure ends with "END;" 
6.  A procedure may have one or more commands ("END;" is not a command).
 It takes one time unit to execute one command.
7.  A command is of one of the following formats:
l   "NOP;" The program will go to execute the next line in the next time 
unit.
l   "IF x>[threshold] GOTO [line number];" The program takes a value x 
from [0..1) randomly. If x is larger than the [threshold], the program 
will execute the [line number] in the next time unit, otherwise, the 
program execute the next line in the next time unit.
l   "IF x<[threshold] GOTO [line number];"  The program takes a value x 
from [0..1) randomly. If x is smaller than the [threshold], the 
program will execute the [line number] in the next time unit, otherwise,
 the program execute the next line in the next time unit.
l   "IF x>[threshold] PROC [procedure name];" The program takes a value 
x from [0..1) randomly. If x is larger than the [threshold], the program
 will execute the procedure with [procedure name], then come back to the
 next line after the current command in this procedure.
l   "IF x<[threshold] PROC [procedure name];" The program takes a value 
x from [0..1) randomly. If x is smaller than the [threshold], the 
program will execute the procedure with [procedure name], then come back
 to the next line after the current command in this procedure.
8.  The program finishes one procedure whenever it sees the "END;".
9.  In each procedure, the line number starts with 1. That is, the 
first command in a procedure is "line 1", the second is "line 2". "END;"
 is the last line in a procedure.

The Evaluator takes one random program as input; return the expected 
runtime of some procedures upon requests, with an accuracy of 3 digits 
after the decimal point.

To make your lives easier, we have the following simplification:
1.  The condition of "IF" is always a comparison between a random 
variable and a constant threshold.
2.  Random Variables in different "IF" clause are independent. Even there
 may be more than one "IF x>0.5" in one procedure, the "x"s in different
 commands are independent.
3.  There is no loop-reference (including indirect loop reference) 
between different procedures.
4.  For each command, the probability that the program starts from this 
command and ends at the end of the procedure is positive. That means, 
you can finally reach the end of a procedure from any command.
5.  There are more than 1 and less than 100 procedures in a program
6.  All the strings in this problem are within 100 characters.

Input
The input file contains one random program described as above with one 
or more random procedures, and one or more requests. The requests are 
following the program. Each request is a line with one string, which 
is the name of the requested procedure. The request list ends with a 
line containing “REQUEST_END” (there is no procedure with a name as “
REQUEST_END”)
Output
For each request, output a line with a number presents the expected 
running time of the requested procedure. The accuracy is up to 3 
digits after decimal point.
 

Sample input    Output for the sample input
PROG_STARTPROC AIF x>0.5 GOTO 3;NOP;END;PROC BIF x<0.5 PROC A;NOP;END;
PROG_ENDBAREQUEST_END   2.7501.500
 
Problem C: Radar Installation
(input file: radar.in)

Assume the coasting is an infinite straight line. Land is in one side of
 coasting, sea in the other. Each small island is a point locating in 
the sea side. And any radar installation, locating on the coasting, 
can only cover d distance, so an island in the sea can be covered by a 
radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis.
 The sea side is above x-axis, and the land side below. Given the 
position of each island in the sea, and given the distance of the 
coverage of the radar installation, your task is to write a program to 
find the minimal number of radar installations to cover all the islands.
 Note that the position of an island is represented by its x-y 
coordinates.
 
Input
The input consists of several test cases. The first line of each case 
contains two integers n (1￡n￡1000) and d, where n is the number of 
islands in the sea and d is the distance of coverage of the radar 
installation. This is followed by n lines each containing two integers 
representing the coordinate of the position of each island. Then a blank
 line follows to separate the cases.
The input is terminated by a line containing pair of zeros.
Output
For each test case output one line consisting of the test case number 
followed by the minimal number of radar installations needed. “-1” 
installation means no solution for that case.

Sample Input    Output for the sample input
3 21 2-3 12 11 20 20 0  Case 1: 2Case 2: 1

 
Problem D: Holedox Moving
(input file: holedox.in)

During winter, the most hungry and severe time, Holedox sleeps in its 
lair. When spring comes, Holedox wakes up, moves to the exit of its 
lair, comes out, and begins its new life.

Holedox is a special snake, but its body is not very long. Its lair is 
like a maze and can be imagined as a rectangle with n*m squares. Each 
square is either a stone or a vacant place, and only vacant places allow
 Holedox to move in. Using ordered pair of row and column number of 
the lair, the square of exit located at (1,1). 

Holedox’s body, whose length is L, can be represented block by block. 
And let B1(r1,c1) B2(r2,c2) .. BL(rL,cL) denote its L length body, where
 Bi is adjacent to Bi+1 in the lair for 1￡i￡L-1, and B1 is its head, 
BL is its tail. 

To move in the lair, Holedox chooses an adjacent vacant square of its 
head, which is neither a stone nor occupied by its body. Then it moves 
the head into the vacant square, and at the same time, each other 
block of its body is moved into the square occupied by the corresponding
 previous block. 

For example, in the Figure 2, at the beginning the body of Holedox can 
be represented as B1(4,1) B2(4,2) B3(3,2)B4(3,1). During the next step,
 observing that B1’(5,1) is the only square that the head can be 
moved into, Holedox moves its head into B1’(5,1), then moves B2 into 
B1, B3 into B2, and B4 into B3. Thus after one step, the body of Holedox
 locates in B1(5,1)B2(4,1)B3(4,2) B4(3,2) (see the Figure 3).

Given the map of the lair and the original location of each block of 
Holedox’s body, your task is to write a program to tell the minimal 
number of steps that Holedox has to take to move its head to reach the 
square of exit (1,1).
 

Input
The input consists of several test cases. The first line of each case 
contains three integers n, m (1￡n, m￡20) and L (2￡L￡8), representing
 the number of rows in the lair, the number of columns in the lair and 
the body length of Holedox, respectively. The next L lines contain a 
pair of row and column number each, indicating the original position 
of each block of Holedox’s body, from B1(r1,c1) to BL(rL,cL) orderly, 
where 1￡ri￡n, and 1￡ci￡m,1￡i￡L. The next line contains an 
integer K, representing the number of squares of stones in the lair. The
 following K lines contain a pair of row and column number each, 
indicating the location of each square of stone. Then a blank line 
follows to separate the cases.
The input is terminated by a line with three zeros.
Note: Bi is always adjacent to Bi+1 (1￡i￡L-1) and exit square (1,1) 
will never be a stone.
Output
For each test case output one line containing the test case number 
followed by the minimal number of steps Holedox has to take. “-1” 
means no solution for that case.
 

Sample input    Output for the sample input
5 6 44 14 23 23 132 33 33 44 4 42 31 31 42 442 12 23 44 20 0 0  Case 1: 
9Case 2: -1
Note: In the above sample case, the head of Holedox can follows (4,1)à
(5,1)à(5,2)à(5,3)à(4,3)à(4,2)à(4,1)à(3,1)à(2,1)à(1,1) to reach 
the square of exit with minimal number of step, which is nine.
 
Problem E: Game Prediction
(input file: game.in)

Suppose there are M people, including you, playing a special card game.
 At the beginning, each player receives N cards. The pip of a card is 
a positive integer which is at most N*M. And there are no two cards with
 the same pip. During a round, each player chooses one card to compare 
with others. The player whose card with the biggest pip wins the round,
 and then the next round begins. After N rounds, when all the cards of 
each player have been chosen, the player who has won the most rounds 
is the winner of the game.

Given your cards received at the beginning, write a program to tell 
the maximal number of rounds that you may at least win during the 
whole game.
Input
The input consists of several test cases. The first line of each case 
contains two integers m (2￡m￡20) and n (1￡n￡50), representing the 
number of players and the number of cards each player receives at the 
beginning of the game, respectively. This followed by a line with n 
positive integers, representing the pips of cards you received at the 
beginning. Then a blank line follows to separate the cases. 
The input is terminated by a line with two zeros.
Output
For each test case, output a line consisting of the test case number 
followed by the number of rounds you will at least win during the game.


Sample input    Output for the Sample Input
2 51 7 2 10 96 1162 63 54 66 65 61 57 56 50 53 480 0    Case 1: 2Case 2: 
4
 
Problem F: Chocolate
(input file: chocolate.in)

In 2100, ACM chocolate will be one of the favorite foods in the world.
“Green, orange, brown, red…”, colorful sugar-coated shell maybe is 
the most attractive feature of ACM chocolate. How many colors have you 
ever seen? Nowadays, it’s said that the ACM chooses from a palette of 
twenty-four colors to paint their delicious candy bits.
One day, Sandy played a game on a big package of ACM chocolates which 
contains five colors (green, orange, brown, red and yellow). Each time 
he took one chocolate from the package and placed it on the table. If 
there were two chocolates of the same color on the table, he ate both of
 them. He found a quite interesting thing that in most of the time there
 were always 2 or 3 chocolates on the table. 
Now, here comes the problem, if there are C colors of ACM chocolates 
in the package (colors are distributed evenly), after N chocolates are 
taken from the package, what’s the probability that there is exactly 
M chocolates on the table? Would you please write a program to figure it
 out?

Input
The input file for this problem contains several test cases, one per 
line.
For each case, there are three non-negative integers: C (C <= 100), N 
and M (N, M <= 1000000).
The input is terminated by a line containing a single zero.
Output
The output should be one real number per line, shows the probability for
 each case, round to three decimal places.

Sample input    Output for the sample input
5 100 20    0.625
Problem G: Machine Schedule
(input file: machine.in)

As we all know, machine scheduling is a very classical problem in 
computer science and has been studied for a very long history. 
Scheduling problems differ widely in the nature of the constraints 
that must be satisfied and the type of schedule desired. Here we 
consider a 2-machine scheduling problem.
There are two machines A and B. Machine A has n kinds of working modes,
 which is called mode_0, mode_1, …, mode_n-1, likewise machine B has 
m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the 
beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two
 machines in particular mode. For example, job 0 can either be processed
 in machine A at mode_3 or in machine B at mode_4, job 1 can either be 
processed in machine A at mode_2 or in machine B at mode_4, and so on. 
Thus, for job i, the constraint can be represent as a triple (i, x, y),
 which means it can be processed either in machine A at mode_x, or in 
machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine’
s working mode from time to time, but unfortunately, the machine’s 
working mode can only be changed by restarting it manually. By 
changing the sequence of the jobs and assigning each job to a suitable 
machine, please write a program to minimize the times of restarting 
machines. 

Input
The input file for this program consists of several configurations. 
The first line of one configuration contains three positive integers: n,
 m (n, m < 100) and k (k < 1000). The following k lines give the 
constrains of the k jobs, each line is a triple: i, x, y.
The input will be terminated by a line containing a single zero.
Output
The output should be one integer per line, which means the minimal times
 of restarting machine.
 

Sample input    Output for the sample input
5 5 100 1 11 1 22 1 33 1 44 2 15 2 26 2 37 2 48 3 39 4 30   3

 
Problem H: Mileage Bank
(input file: mileage.in)

Mileage program of ACM (Airline of Charming Merlion) is really nice 
for the travelers flying frequently. Once you complete a flight with 
ACM, you can earn ACMPerk miles in your ACM Mileage Bank depended on 
mileage you actual fly. In addition, you can use the ACMPerk mileage 
in your Mileage Bank to exchange free flight ticket of ACM in future. 

The following table helps you calculate how many ACMPerk miles you can 
earn when you fly on ACM.

When you fly ACM    Class Code  You’ll earn
First Class F   Actual mileage + 100% mileage Bonus
Business Class  B   Actual mileage + 50% mileage Bonus
Economy Class1-500 miles500+ miles  Y   500 milesActual mileage

    It’s shown that your ACMPerk mileage consists of two parts. One is 
your actual flight mileage (the minimum ACMPerk mileage for Economy 
Class for one flight is 500 miles), the other is the mileage bonus 
(its accuracy is up to 1 mile) when you fly in Business Class and 
First Class. For example, you can earn 1329 ACMPerk miles, 1994 
ACMPerk miles and 2658 ACMPerk miles for Y, B or F class respectively 
for the fly from Beijing to Tokyo (the actual mileage between Beijing 
and Tokyo is 1329 miles). When you fly from Shanghai to Wuhan, you can 
earn ACMPerk 500 miles for economy class and ACMPerk 650 miles for 
business class (the actual mileage between Shanghai and Wuhan is 433 
miles).

    Your task is to help ACM build a program for automatic calculation of 
ACMPerk mileage.

Input
The input file contains several data cases. Each case has many flight 
records, each per line. The flight record is in the following format: 
OriginalCity DistanceCity ActualMiles ClassCode
Each case ends with a line of one zero. 
A line of one # presents the end of the input file.
Output
Output the summary of ACMPerk mileages for each test case, one per 
line.

Sample input    Output for the sample input
Beijing Tokyo 1329 FShanghai Wuhan 433 Y0#  3158