Pendulum

PENDULUM.C PENDULUM.CPP PENDULUM.PAS

Consider a pendulum hanging on a string from a hook on a wall. When pushed, this pendulum will swing back and forth. Now imagine other hooks on the wall, placed in the path of our pendulum's string. The pendulum will bend around them, possibly even loop around them. In general, it will follow a much more complex path than before. After some time, the pendulum's motion will repeat, the pendulum will follow a periodic orbit. What we would like you to do is to compute the distance travelled by the pendulum as it completes one cycle of the orbit.

More formally, we place a cartesian coordinate system on the wall. The pendulum's string is affixed at the origin (0,0). As usual, the x-axis points to the right and the y-axis points upwards. The string of the pendulum has a length of r. The pendulum is released at position (-r,0) and therefore starts swinging to the right. Furthermore, there are n additional hooks distributed over the plane which may influence the path of the pendulum.

In our ideal world, the following assumptions are true:

The diameters of the hooks and of the string are zero.
The pendulum loses no energy (e.g. by friction).
The pendulum will never hit a hook, only its string will.
The pendulum's string is made of some futuristic material that only bends where it touches a hook but is otherwise rigid.

Your program should simulate the movement of the pendulum and output the spatial length of the periodic orbit that it finally enters. As you may remember from physics: due to gravity, the pendulum will never reach a height greater than the one it started from! That is, it will never get above the x-axis. It will either reach its initial height again or circle endlessly around a hook in the wall.

Input

The input file contains several test cases. Each case begins with a line containing an integer n (the number of hooks, 1 <= N <= 50) and a real r (the length of the pendulum's string). The following n lines each contain two integers specifying the x- and y-coordinate of the corresponding hook.

The file ends with a case having r = 0, which should not be processed.

Output

For each case output a line containing the number of the case (`Pendulum #1', `Pendulum #2', etc.).

Then print a line that contains the distance which the pendulum travels for completing one cycle of its periodic orbit. Do not count the distance travelled to reach the starting point of the orbit. (Adhere to the format shown in the output sample.) The distance should be exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input

2 16.0

3 -4

-3 -4

1 18.0

5 -12

0 0

Sample Output

Pendulum #1

Length of periodic orbit = 87.66

Pendulum #2

Length of periodic orbit = 31.42

Indexing

INDEXING.C INDEXING.CPP INDEXING.PAS

Input

Consider several lines of text written with capital letters and one character called KEY, specified on a line preceding the text. The words in the text are separated by spaces. The maximum word length is <= 80. There are no words splitted between two lines. The line length is also <= 80.

Output

Write a program to display an index of all words within the text starting with the KEY. The index must be alphabetically sorted. Each word appears in the index only once and must be followed by the numbers of all the lines in which it appears. Only a single occurrence of each word on a line must be included in the index.

Sample Input

CONSIDER SEVERAL LINES OF TEXT AND ONE CHARACTER CALLED KEY,

SPECIFIED ON A LINE PRECEDING THE TEXT. THE WORDS IN THE TEXT ARE

SEPARATED BY SINGLE SPACE. THERE ARE NO WORDS SPLITTED BETWEEN TWO

LINES.

WRITE A PROGRAM TO DISPLAY AN INDEX OF ALL WORDS WITHIN THE TEXT

STARTING WITH THE KEY. THE INDEX MUST BE ALPHABETICALLY SORTED. EACH

WORD IN THE INDEX MUST BE FOLLOWED BY THE LIST OF THE LINE NUMBERS IN

WHICH IT APPEARS.

Sample Output

TEXT 1 2 5

THE 2 5 6 7

THERE 3

TO 5

TWO 3

What is the Median?

MEDIAN.C MEDIAN.CPP MEDIAN.PAS

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers.

Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}.

If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4!

Input

The input file consists of series of integers X ( 0 <= X < 2^31 ) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.

Output

For each input print the current value of the median.

Sample Input

Sample Output

The Tower of Babylon

BABYLON.C BABYLON.CPP BABYLON.PAS

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (x_i, y_i, z_i). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

Input and Output

The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values x_i, y_i and z_i.

Input is terminated by a value of zero (0) for n.

For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height"

Sample Input

10 20 30

6 8 10

5 5 5

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

31 41 59

26 53 58

97 93 23

84 62 64

33 83 27

Sample Output

Case 1: maximum height = 40

Case 2: maximum height = 21

Case 3: maximum height = 28

Case 4: maximum height = 342

The Return of the Roman Empire

ROMAN.C ROMAN.CPP ROMAN.PAS

Input and Output

Write a program that accepts Roman numerals (one per line) and converts them to decimal form.

Remember, I=1, V=5, X=10, L=50, C=100, D=500, and M=1000. Furthermore, there are the following digraphs: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. There may be at most three consecutive I, X, C or M. Thus the greatest possible number is 3999.

The program should reject improperly formed numerals.

Sample Input

MCMXCVIII

CCM

Sample Output

This is not a valid number