L3/M1, 2005–2006

Algorithmique effective – TD 11 Divers

1 Un petit jeu

Exercice 1 Joseph. UVa : 305. The Joseph’s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, …, n, standing in circle every m-th is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. Output

The output file will consist of separate lines containing m corresponding to k in the input file. Sample Input

3
4
0

Sample Output

5
30

2 Pendule

Exercice 2 Pendulum. UVa : 319. 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, ) 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

3 Un problème rationnel

Exercice 3 Rational Numbers from Repeating Fractions. UVa : 332. A rational number is any which can be written in the form p/q, where p and q are integers. All rational numbers less than 1 (that is, those for which p is less than q) can be expanded into a decimal fraction, but this expansion may require repetition of some number of trailing digits. For example, the rational number 7/22 has the decimal expansion .3181818 … Note that the pair of digits 1 and 8 repeat ad infinitum. Numbers with such repeating decimal expansions are usually written with a horizontal bar over the repeated digits, like this: .3\overline{18}.

If we are given the decimal expansion of a rational fraction (with an indication of which digits are repeated, if necessary), we can determine the rational fraction (that is, the integer values of p and q in p/q) using the following algorithm.

Assume there are k digits immediately after the decimal point that are not repeated, followed by a group of j digits which must be repeated. Thus for 7/22 we would have k = 1 (for the digit 3) and j = 2 (for the digits 1 and 8). Now if we let X be the original number (7/22), we can compute the numerator and denominator of the expression

\frac{10^{k+j} × X − 10^{k} × X}{10^{k+j} − 10^{k}} .

For .3\overline{18} we obtain the following calculation for the numerator of this fraction:

10^{3} × .3\overline{18} − 10^{1} × .3\overline{18} = 318.\overline{18} − 3.\overline{18} = 315.

The denominator is just 1000−10, or 990. It is important to note that the expression in the numerator and the denominator of this expression will always yield integer values, and these represent the numerator and denominator of the rational number. Thus the repeated fraction .3\overline{18} is the decimal expansion of the rational number 315/990. Properly reduced, this fraction is (as expected) just 7/22. Input

The input data for this problem will be a sequence of test cases, each test case appearing on a line by itself, followed by a −1. Each test case will begin with an integer giving the value of j, one or more spaces, then the decimal expansion of a fraction given in the form 0.ddddd (where d represents a decimal digit). There may be as many as nine (9) digits in the decimal expansion (that is, the value of k + j may be as large as 9). Output

For each test case, display the case number (they are numbered sequentially starting with 1) and the resulting rational number in the form p/q, properly reduced. Sample Input

2 0.318
1 0.3
2 0.09
6 0.714285
-1

Sample Output

Case 1: 7/22
Case 2: 1/3
Case 3: 1/11
Case 4: 5/7