Problem a addition Chains

Problem B

Binomial Showdown

In how many ways can you choose k elements out of n elements, not taking order into account?

Input Specification

Output Specification

Sample Input

10 5

0 0

Sample Output

252

1997/98 ACM International Collegiate Programming Contest

Problem C

Compromise

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

Output Specification

Sample Input

sind fuer die abgeordneten ein buch mit sieben siegeln

um dem abzuhelfen

muessen dringend alle subventionsgesetze verbessert werden

#

die steuern auf vermoegen und einkommen

nachdruecklich erhoben werden

dazu muessen die kontrollbefugnisse der finanzbehoerden

dringend verbessert werden

#

Sample Output

1997/98 ACM International Collegiate Programming Contest

Problem D

Dungeon Master

Source file: dungeon.(c|C|pas)
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.(c|C|pas)
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 non-linear 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 sub-expressions of an equation will be linear in x too. That means, there won't be test cases like x*x-x*x+x=0 which is a linear equation but contains non-linear sub-expressions (x*x).

Note that all numbers occuring in the input are non-negative 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

(42-6*7)*x=2*5-10

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.(c|C|pas)
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 n-2 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.(c|C|pas)
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 white-space 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.(c|C|pas)
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

Directory: downloads94 -> ebook -> 378567
378567 -> Problem a arbitrage

Download 45.56 Kb.

Share with your friends: