The 2000 ACM Asia Programming Contest
 
 

The 2000 ACM Asia Programming Contest, Kanpur Site
December 16, 2000
Rules:
1. There are eight problems for each team to be completed in five hours.
2. All problems require you to read test data from the standard input and write the results to the
standard output.
3. The name of the file containing the sample input given for each problem. If you test your program
using PC2, it will automatically redirect input from the sample input file to your program.
4. Output must correspond exactly to the provided sample output, including (mis)spellings and
spacing. Multiple spaces will not be used in any of the judges? output, except where explicitly
stated.
5. Programming style is not considered in this contest. You are free to code in whatever style you
prefer. Documentation is not required.
6. Contestant teams must submit their program through PC2 software.
7. Contestants may use books and manuals. Nothing else is allowed.
8. Judges? decisions are final.
Tip: Try to solve the easiest problem first.
Problem A
Boundary Walls
Sample Input: boundary.in
A cooperative society has purchased some land for distribution amongst its members. The land is divided into plots so that
every member can get a plot. It is planned to mark each plot by a two meter high boundary wall. The boundary of each plot is
shaped like a polygon (not necessarily a convex one). (The figure below shows a land with five plots.) It is divided into line
segments such that any two line segments either intersect at an end point or do not intersect at all (there may be co-linear
segments present). A builder has been hired to construct the boundary walls. He has put different groups of workers to work
on different segments of the boundary wall (a segment of boundary wall corresponds to a line segment in the boundary of a
plot). All the groups, at the end of the day, submit their report to the contractor indicating whether their work is finished or
not. Write a program to help identify the builder the number of plots for which the work has been completed.
Input
The first line of the input gives the number of test cases T.
For each test case, the first line contains an integer N (between 3 and 50) giving the number of line segments in the land. The
j-th of the next N lines contains five integers a, b, c, d, and e where (a, b) and (c, d) give the coordinates of the corner point
of the j-th line segment and the number e is 1 if that boundary wall segment is complete, 0 otherwise.
Output
For each test case, there is one line in the output giving the number of plots on which work is completed.
Sample Input
2
5
0 0 0 1 0
0 0 1 0 1
0 1 1 1 1
1 0 1 1 1
0 0 1 1 1
7
0 0 2 0 1
0 0 0 1 1
2 0 2 2 1
2 2 1 2 1
1 2 0 1 1
1 2 1 1 1
0 1 1 1 1
Sample Output
1
2
PROBLEM B
Ski Slopes
Sample Input: ski.in
A skier wants to ski down from the top of a mountain to its base. There are several possible routes, using different slopes
enroute, and passing through some flat areas. The effort expended in skiing down a slope depends upon the length of the
slope and the speed of skiing. For each slope, there is a maximum advisable speed. The skier wants to use a route that
minimizes the average effort spent per unit distance traveled (i.e., the total effort expended divided by the total distance
traveled).
You are given the map of the mountain slopes. That is, the flat areas and the slopes connecting these areas are given. Note
that on a slope, one can only ski downwards. For each slope, you are also given the length of the slope and the maximum
advisable speed for it. The effort expanded in skiing down a particular slope is given by the following formula.
e = d*(70 - s) if s £ 60, and e = d*(s - 50) if s > 60
where e is the effort required, d is the distance traveled, and s is the speed of travel.
You have to determine the minimum average effort per unit distance that the skier has to expend in order to reach the
mountain base, while staying within the maximum advisable speed at every slope.
Input
The input may have multiple test cases. The first line of input gives the number of test cases T. For each test case, the first
line of input gives the number of flats, N (N £ 100), and the number of slopes, R (R £ 10000), connecting them respectively.
The flats are assumed to be numbered from 1 to N . The flats at the top and the base of the mountain are assumed to be
numbered 1 and N respectively. Each of the next R lines describes a slope by giving: the numbers of the flats at the top and
the bottom of the slope, the maximum advisable speed for the slope, and the length of the slope respectively.
Output
For each test case, output a single number (to an accuracy of 2 decimal places) that gives the minimum average effort per unit
distance that needs to be expended to ski down from the mountain top to the base. The output for each test case should be on
a separate line.
Sample Input
2
4 5
1 4
1 4 30 60
1 2 50 40
1 3 60 20
2 4 60 50
3 4 50 50
3 3
1 3
1 2 50 40
1 3 40 20
2 3 20 30
Sample Output
14.44
30.00
PROBLEM C
The Monkey Dance
Sample Input: dance.in
The director of Hind Circus has decided to add a new performance, the monkey dance, to his show. The monkey dance is
danced simultaneously by N monkeys. There are N circles drawn on the ground. In the beginning, each monkey sits on a
different circle. There are N arrows drawn from circle to circle in such a way that in each circle, exactly one arrow starts and
exactly one ends. No arrow can both begin and end at the same circle. When the show begins, at each whistle of the
ringmaster, all the monkeys simultaneously jump from their respective circles to other circles following the arrows from their
respective current circles. This is one step of the dance. The dance ends when all the monkeys have returned to the circles
where they initially started. The director wishes the dance to last as many steps as possible. This can be achieved by drawing
the arrows intelligently. Given N, you have to write a program to determine the maximum possible number of steps such that
there is a way of drawing the arrows to make the dance last these many steps.
Input
The input may have multiple cases. Each case consists of just the value of N (N £ 40) on a separate line. The input ends with
a 0 for the value of N.
Output
For each case, simply output the maximum possible number of steps. Each output should be on a separate line.
Sample Input
5
8
0
Sample Output
6
15
Problem D
Error Correcting Polynomials
Sample Input: polynomial.in
Error correction is extremely useful in recovering from corrupted data. The abstract setting for this problem is: given a set of
n data elements such that at least t of the data elements are uncorrupted, recover the complete uncorrupted data from it. To be
able to do such a correction, data elements need to be of special form. Such forms are called Error-correcting codes. An
error-correcting code that is widely used is as follows: the data elements are evaluations of a univariate polynomial of degree
d modulo a prime number p. The error-correction algorithm for this code was very complex until Madhu Sudan discovered a
nice way of doing this. His algorithm is: given a set of n points y1, ?, yn (each value is between 0 and p-1, and also n < p)
with at least t of the ys correct (this means that for the correct yj, yj = P(j) for some unknown degree d polynomial modulo p)
do the following:
1. Construct a non-zero polynomial in two variables Q(x, y) with the degree of y being e and the degree of x being f and
(e +1)* ( f +1) > n and e * d + f < t for which Q(j, yj) = 0 for every j between 1 and n. The exact values of e and f are
determined using t, d, and n.
2. Factor the polynomial Q into irreducible factors.
3. Consider all the factors of the form (y - g(x)) such that degree of g is d and identify one for which yj = g(j) for at least t
values.
This identified polynomial, g , is the desired one. Once the polynomial is identified, all the correct values of y can be
recovered by computing g(j) for every j.
Madhu Sudan has written programs for factoring the two variable polynomial and for identifying the right polynomial as well
as computed the right values of e and f . He now just needs a program that constructs the two variable polynomial Q. Please
help him in writing this program.
Input
The number of test cases T is written in the first line of the input.
For each test case, the first line contains the value of n, p, e, and f (all these are between 1 and 100 satisfying the constraints
mentioned above; in particular, p is always a prime number) in that order. The j-th of the next n lines contains the value yj.
Output
For each test case, output all the coefficients of the polynomial Q in the following order: first output all the coefficients of the
terms in which the degree of y is zero and order these coefficients by increasing degree of x; then output all the coefficients
of the terms in which degree of y is one ordering these in the same way as before, and so on. Each coefficient must be on a
separate line. If there are more than one solutions, output any one.
The output of different test cases must be separated by a blank line.
Sample Input
2
3 7 1 1
6
4
5
4 11 1 2
2
3
0
0
Sample Output
0
4
3
1
1
4
1
2
6
0
Problem E
Spaceship Travel
Sample Input: space.in
A spaceship is to be launched from the Earth to visit a number of planets. The order of visiting the planets is fixed. The
spaceship can travel from one planet to another via normal space or via hyperspace. Hyperspace travel reduces the traveled
distance substantially, however, the fuel consumption during the hyperspace travel is much more. In fact, if the spaceship
travels d light years thorough the hyperspace, then the fuel consumed is d4 units! For d light years traveled through
normal space, the fuel consumed is just d units. Also, between two planets, the spaceship can either
travel via hyperspace or normal space but not both. Design an algorithm that determines a way of
traveling that minimizes the fuel consumption.
Input
The first line of the input file contains a number T giving the number of test cases to follow.
The first line of each test case contains an integer N (between 1 and 50) giving the number of planets to be visited. The j-th of
the next N lines correspond to the j-th planet to be visited and contains two integers hd and nd denoting respectively the
hyperspace and normal space distance between the (j-1)-th planet and j-th planet (the 0-th planet is taken to be the Earth). The
number hd is between 1 and 10 light years and the number nd is between 1 light year and 10 million light years.
Output
For each test case in the input, output a number giving the minimum units of fuel required to visit all the planets. Each test
case output must be on a separate line.
Sample Input
2
3
3 1000
2 5000
4 8000
5
1 10000
2 3547
7 36782
4 2178
9 67428
Sample Output
2296
52507
Problem F
Maze
Sample Input: maze.in
One day, looking at old documents inherited from his grandfather, Ramesh discovers a map. Reading the accompanying
document, he realizes that the map is of a complex maze of chambers and passages inside a mountain. Chambers in this maze
have doors opening to passages leading to other chambers. All the doors have one peculiarity: they have handles only on one
side, and so can be opened either from the chamber or from the passage but not both. The passages leading from any chamber
have been designed in such a way that either there is only one passage leading out or there is a passage such that upon
following it one can never come back to the chamber. Also, there is at most one passage between any two chambers. On the
ceiling of each chamber, a number is written. There are two special chambers: the entry chamber and the exit chamber. The
entry chamber can be entered via a door from outside the mountain and the exit chamber has a door that leads to a secret
chamber. The exit door opens only upon reciting a magic sequence of numbers. It is given that this sequence is the only
sequence of numbers satisfying the following properties:
The sequence can be constructed by noting the numbers written in chambers, in that order, on a path from entry
chamber to exit chamber.
The numbers in the sequence are all distinct.
If any chamber has a number from this sequence written, then there is a path from the chamber to the exit chamber
such that all the chambers in this path contain numbers only from this sequence.
Design an algorithm to help Ramesh reach the secret chamber.
Input
The first line of the input consists of an integer T giving the number of test cases to follow.
The first line of each test case contains two integers N (between 1 and 100) and P (between 1 and 1000) giving the number of
chambers and the number of passages in the maze respectively. The next line contains N numbers: the j-th number is written
in the j-th chamber. Each of the next P lines contain four numbers a, b, c, d with a, b between 1 and N and c, d having binary
value, giving that there is a passage between chamber number a and chamber number b such that the door to the passage from
chamber a opens from inside the chamber iff c = 1 and the door to the passage from chamber b opens from inside the
chamber iff d = 1. The last line of the test case contains two numbers s and t with s being the entry chamber number and t
being the exit chamber number.
Output
For each test case in the input, there is one output line that contains the magic sequence with numbers separated by blanks.
Sample Input
2
6 6
9 10 11 12 13 14
1 2 1 0
2 3 1 0
3 4 1 0
4 5 1 0
4 6 1 0
4 2 1 0
1 5
10 13
22 81 84 84 72 60 63 62 99 54
1 2 1 0
1 4 1 1
2 4 1 0
2 5 1 0
5 3 0 1
6 3 0 1
4 7 1 0
8 4 0 1
5 2 1 0
5 8 1 0
9 5 0 1
9 6 0 1
10 6 0 1
1 9
Sample Output
9 10 11 12 13
22 81 72 99
Problem G
Terrain Traversal
Sample Input: terrain.in
A battalion of tanks is to be sent to a border post from the base. There are no obstructions between the base and the border
post and so the tanks can travel in any direction. However, the terrain between the base and the border post is of two kind:
first comes the muddy terrain and then the desert. The maximum velocity of a tank in each of these terrains is different. It is
assumed that a straight line separates the two terrains. Design an algorithm that finds out the fastest route to the border post.
Input
There are several test cases. The first line of the input contains the number of test cases T.
For each test case, the first line has two numbers u and v with u being the maximum velocity (in kilometers per hour) of a
tank in the desert and v the maximum velocity in the muddy terrain. The next line contains the coordinates of the border post
assuming the dividing line between the terrains to be the x-axis (the y-coordinate of the border post is always positive). The
third line contains the coordinates of the base camp (the y-coordinate of the base camp is always negative). The unit of the
coordinates is kilometers.
Output
For each test case, there is one output line containing two numbers: the first number denotes the time taken in seconds
(rounded off to the closest second) by a tank to reach the border post by the fastest route. The second number denotes the
x-coordinate (in kilometers, with an accuracy of three decimal digits) of the point where the tank crosses over to the desert.
Sample Input
2
1 1
5 3
5 -2
3 5
20 10
8 -9
Sample Output
18000 5.000
21590 15.688
Problem H
Acid Containers
Sample Input: acid.in
Company ACIDIC manufactures acid. The acid is filled into containers and sent out to different places. Sometimes, the
containers start leaking. To handle such situations, the company has a room with several container holders. These holders are
arranged in a rectangle grid. Each of these can hold one leaky container and absorb the acid leakage. After all the acid has
leaked out, the containers are taken out and the leak point(s) are fixed. One day, the leaky containers were put in some of the
holders. After a while, some more leaky containers were detected and brought to the room. The supervisor handling this then
realized that all the containers that are present in the room are leaking very heavily. So heavily that they have corroded their
holders and in a short time they would also corrode all the holders in the room in the directions of the leak. The containers are
leaking either in the North-South direction or in the East-West direction. (The figure above shows a room with a 4-by-6 grid
of holders having four leaky containers. The dashed arrows represent the direction of leakage.) The supervisor tried to
remove containers from their holders but could not as they were stuck to the holders. However, he could rotate the containers
so that the direction of leakage could be changed from North-South to East-West or vice-versa. The supervisor suspects that
the current lot of leaky containers may also start to leak heavily. Help the supervisor find the rotations of existing containers
and placement of current lot of containers so that the number of corroded holders is minimized.
Input
There are several test cases. The first line of the input contains the number of test cases T.
For each test case, the first line has four numbers R, C, N and M. Numbers R and C (between 10 and 100) give the number of
rows and columns in the grid. Number N (between 1 and 20) gives the number of leaky containers in the room and number M
(between 1 and 20) gives the number of leaky containers in the current lot. Each of the next N lines gives the placement and
the leakage direction of an existing container. These are given as three numbers a, b, and c where a (between 1 and R) is the
row number (counting from top), b (between 1 and C) is the column number (counting from left), and c is 1 if the leakage
direction is North-South, 0 otherwise.
Output
For each test case, the output should be a number giving the smallest number of holders that will get corroded after rotating
the existing containers and placing the containers in the current lot (assuming the all the current lot containers will also leak
heavily). The output for different test cases should be on different lines.
Sample Input
2
4 6 4 4
1 2 0
2 4 0
3 2 1
3 5 1
50 50 5 10
1 35 1
17 44 0
17 46 1
42 35 1
42 46 0
Sample Output
12
148