Rohith and Circles
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has a friend named Rohith who is very good at geometry. One day Chef came across an interesting problem on the topic of circles and shared it with Rohith.
Next day Rohith also came up to chef with a problem he just created. When our chef couldn't solve it thinking that it uses some advanced geometry, Rohith took the pleasure saying that the solution of this problem uses exactly the same concept which was used to solve the problem that they have discussed the day before. This came as a shock to our chef and he became desperate to solve this problem, but even as he tried a lot, he couldn't solve it. Rohith doesn't want to share his solution, so can you help our chef in solving the problem?
Take a deep breath! You are going to draw a lot of circles.
The problem goes like this:
- First draw a circle of radius R1 on a sheet of paper, let us call it C1.
- Draw another circle of radius R2 touching the circle C1 from the inside (it is given that R2 ≤ R1), let's call this circle as C2.
- Draw another circle of radius R3 such that it touches the circle C1 from inside and the circle C2 from outside (it is given that R3 + R2 ≤ R1), let's call this circle as C3.
- Draw another circle of radius R4 which will touch the circles C2 and C3 externally and the circle C1 internally, let's call it as C4. It is guaranteed that such a set of circles can be drawn.
- Now try to draw a circle C5 which will touch the circles C2 and C4 externally and the circle C1 internally. Note that circles C5 and C3 are not the same (see the picture below for more clarification). Let its radius be R5
- Now try to draw a circle C6 which will touch the circles C2 and C5 externally and the circle C1 internally. Let its radius be C6.
- And so on, like this, draw N circles such that the circle CN will touch circles C2, CN - 1 externally and the circle C1 internally. Let its radius be RN
After drawing the four circles, the figure may look something like this:
After drawing all the circles the figure may look like this
You are given N, R1, R2, R3 and R4, you need to find the radius of the circle CN, i.e, RN.
You are given four integers N0, P, M, B. There are T test cases in total. Test cases are numbered from 1 to T. The value of N for the tth test case, i.e, Nt = (P * Nt - 1) % M + B. The values of R1, R2, R3 and R4 remain constant over all the test cases.
The first line of the input contains an integer T denoting the number of test cases.
The next line contains four integers N0, P, M and B separated by a single space.
The next line contains four real valued numbers R1, R2, R3 and R4 separated by a single space.
As the number of test cases can be huge, you need to output a single line containing the sum of values of RN over all test cases exactly up to 6 decimal places.
Constraints and Subtasks
Subtask 1: 25 points
- 1 ≤ T ≤ 103
- 1 ≤ Ri ≤ 103
- 1 ≤ N0, P, M, B ≤ 103
Subtask 2: 75 points
- 1 ≤ T ≤ 107
- 1 ≤ Ri ≤ 1012
- 1 ≤ N0, P, M, B ≤ 109
Input: 1 1 2 1 5 6 3 3 2 Output: 1.000000
After drawing 5 circles the figure looks like this.The radius of the circle C5 here is R5 = 1.
|Tags||adurysk, geometry, july15, maths, medium-hard, recurrence|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.