ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Tavrida NU Akai contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. The Island of Bad Luck 2

Time limit: 0.5 second
Memory limit: 64 MB
The natives of an island in the Pacific between 35 and 36 degrees of southern latitude have the following custom. The chief of the tribe draws a line l on the sand. After that all natives can only draw circles that touch the line l. All these circles should lie on the same side of l and no circle should lie inside another circle or have at least two common points with another circle. The natives call two such circles neighbors if and only if they externally touch each other, and there is no circle between them that also touches the line l.
When the line l is drawn, the chief's daughter (let's call her victim) draws two neighboring circles with radii r1 and r2. After that n natives come to the drawing in turns and each of them for each pair of neighboring circles inscribes a new circle that touches the line l and both circles in the pair. At the end all circles are numbered with consecutive integers starting from 1 in the same order as their touching points with line l are situated along line l (circle with radius r1 has number 1). The victim will be eaten if the radius of the i-th circle is rational. Help her find this radius and prepare for her fate in advance.


The only input line contains integers r1, r2, n and i (1 ≤ r1, r2 ≤ 1000; 0 ≤ n ≤ 30; 1 ≤ i ≤ 2n + 1).


If the radius is irrational, output a single line “Irrational”. Otherwise, output in a single line a radius of the i-th circle in the form of irreducible fraction.


1 1 1 2
3 5 2 4
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.
To submit the solution for this problem go to the Problem set: 1812. The Island of Bad Luck 2