1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem A Addition Chains
Source file: addition.(cCpas)
Input file: addition.in
An addition chain for n is an integer sequence _{0}, a_{1},a_{2},...,a_{m}> with the following four properties:
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
The input file will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n.
Output Specification
For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.
Hint: The problem is a little timecritical, so use proper break conditions where necessary to reduce the search space.
Sample Input
5
7
12
15
77
0
Sample Output
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem B Binomial Showdown
Source file: binomial.(cCpas)
Input file: binomial.in
In how many ways can you choose k elements out of n elements, not taking order into account?
Write a program to compute this number.
Input Specification
The input file will contain one or more test cases.
Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n).
Input is terminated by two zeroes for n and k.
Output Specification
For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2^{31}.
Warning: Don't underestimate the problem. The result will fit into an integer  but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.
Sample Input
4 2
10 5
49 6
0 0
Sample Output
6
252
13983816
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem C Compromise
Source file: compromise.(cCpas)
Input file: compromise.in
In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfilled, and this is not a trivial task for the countries (maybe except for Luxembourg). To enforce that Germany will fulfill the criteria, our government has so many wonderful options (raise taxes, sell stocks, revalue the gold reserves,...) that it is really hard to choose what to do.
Therefore the German government requires a program for the following task:
Two politicians each enter their proposal of what to do. The computer then outputs the longest common subsequence of words that occurs in both proposals. As you can see, this is a totally fair compromise (after all, a common sequence of words is something what both people have in mind).
Your country needs this program, so your job is to write it for us.
Input Specification
The input file will contain several test cases.
Each test case consists of two texts. Each text is given as a sequence of lowercase words, separated by whitespace, but with no punctuation. Words will be less than 30 characters long. Both texts will contain less than 100 words and will be terminated by a line containing a single '#'.
Input is terminated by end of file.
Output Specification
For each test case, print the longest common subsequence of words occuring in the two texts. If there is more than one such sequence, any one is acceptable. Separate the words by one blank. After the last word, output a newline character.
Sample Input
die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#
Sample Output
die einkommen der abgeordneten muessen dringend verbessert werden
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem D Dungeon Master
Source file: dungeon.(cCpas)
Input file: dungeon.in
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.
Is an escape possible? If yes, how long will it take?
Input Specification
The input file consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output Specification
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
Sample Output
Escaped in 11 minute(s).
Trapped!
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem E Equation Solver
Source file: equation.(cCpas)
Input file: equation.in
Write a program that can solve linear equations with one variable.
Input Specification
The input file will contain a number of equations, each one on a separate line. All equations are strings of less than 100 characters which strictly adhere to the following grammar (given in EBNF):
Equation := Expression '=' Expression
Expression := Term { ('+'  '') Term }
Term := Factor { '*' Factor }
Factor := Number  'x'  '(' Expression ')'
Number := Digit  Digit Number
Digit := '0'  '1'  ...  '9'
Although the grammar would allow to construct nonlinear equations like "x*x=25", we guarantee that all equations occuring in the input file will be linear in x. We further guarantee that all subexpressions of an equation will be linear in x too. That means, there won't be test cases like x*xx*x+x=0 which is a linear equation but contains nonlinear subexpressions (x*x).
Note that all numbers occuring in the input are nonnegative integers, while the solution for x is a real number.
Output Specification
For each test case, print a line saying "Equation #i (where i is the number of the test case) and a line with one of the following answers:

If the equation has no solution, print "No solution.".

If the equation has infinitely many solutions, print "Infinitely many solutions.".

If the equation has exactly one solution, print "x = solution" where solution is replaced by the appropriate real number (printed to six decimals).
Print a blank line after each test case.
Sample Input
x+x+x=10
4*x+2=19
3*x=3*x+1+2+3
(426*7)*x=2*510
Sample Output
Equation #1
x = 3.333333
Equation #2
x = 4.250000
Equation #3
No solution.
Equation #4
Infinitely many solutions.
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem F Frogger
Source file: frogger.(cCpas)
Input file: frogger.in
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input Specification
The input file will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers x_{i},y_{i} (0 <= x_{i},y_{i} <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output Specification
For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input
2
0 0
3 4
3
17 4
19 4
18 5
0
Sample Output
Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem G Globetrotter
Source file: globetrotter.(cCpas)
Input file: globetrotter.in
As a member of an ACM programming team you'll soon find yourself always traveling around the world: Zürich, Philadelphia, San José, Atlanta,... from 1999 on the Contest Finals even will be on a different continent each year, so one day you might get to Japan or Australia.
At the contest site it would be interesting to know how many miles you are away from home. For this sake, your job is to write a program to compute the geographical distance between two given locations on the Earth's surface.
We assume that the Earth is a perfect sphere with a radius of exactly 6378 km. The geographical distance between A and B is the length of the geodetic line segment connecting A and B.
The geodetic line segment between two points on a sphere is the shortest connecting curve lying entirely in the surface of the sphere.
The value of pi is approximately 3.141592653589793.
Input Specification
The input file will consist of two parts: a list of cities and a list of queries.
City List
The city list consists of up to 100 lines, one line per city. Each line will contain a string c_{i} and two real numbers lat_{i} and long_{i}, representing the city name, its latitude and its longitude, respectively.
The city name will be shorter than 30 characters and will not contain whitespace characters.
The latitude will be between 90 (South Pole) and +90 (North Pole). The longitude will be between 180 and +180 where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.)
The city list will be terminated by a line consisting of a single "#".
Query List
Each line will contain two city names A and B.
The query list will be terminated by the line "# #".
Output Specification
For each query, print a line saying "A  B" where A and B are replaced by the city names. Then print a line saying x km" where x is replaced by the geographical distance (in km) between the two cities, rounded to the nearest integer.
If one of the cities in the query didn't occur in the city list, print a line saying "Unknown" instead. Print a blank line after each query.
Sample Input
Ulm 48.700 10.500
Freiburg 47.700 9.500
Philadelphia 39.883 75.250
SanJose 37.366 121.933
NorthPole 90 0
SouthPole 90 0
#
Ulm Philadelphia
Ulm SanJose
Freiburg Philadelphia
Freiburg SanJose
Ulm Freiburg
SanJose Philadelphia
Ulm LasVegas
Ulm Ulm
Ulm NorthPole
Ulm SouthPole
NorthPole SouthPole
# #
Sample Output
Ulm  Philadelphia
6536 km
Ulm  SanJose
9367 km
Freiburg  Philadelphia
6519 km
Freiburg  SanJose
9412 km
Ulm  Freiburg
134 km
SanJose  Philadelphia
4023 km
Ulm  LasVegas
Unknown
Ulm  Ulm
0 km
Ulm  NorthPole
4597 km
Ulm  SouthPole
15440 km
NorthPole  SouthPole
20037 km
1997/98 ACM International Collegiate Programming Contest
University of Ulm Local Contest
Problem H Tree Recovery
Source file: tree.(cCpas)
Input file: tree.in
Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:
D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F
To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!
Input Specification
The input file will contain one or more test cases.
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
Input is terminated by end of file.
Output Specification
For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).
Sample Input
DBACEGF ABCDEFG
BCAD CBAD
Sample Output
ACBFGED
CDAB
