ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1812. The Island of Bad Luck 2

Test #9
Posted by bsu.mmf.team 4 Feb 2011 02:56
Please, help with this test. I am always getting WA on it.
I did 2 assumptions:
1. If after any iteration the radius becomes irrational - then the answer will be irrational too.
2. The numerator and denominator of resulting fraction both don't exceed 2^64.
Are these assumptions wrong? If so, please, give me some useful tests. The one interesting test I found is:
1 1 30 34785346
3131185849/1170753394542713625
But it doesn't help me much...

Edited by author 04.02.2011 02:56
Re: Test #9
Posted by Alipov Vyacheslav [Tomsk PU] 4 Feb 2011 22:50
The 1st assumption is right.
The 2nd one seems to be wrong. I can't say exactly if the result always fits in int64, but temporary (or itermediate) calculations exceed 2^64 for sure.

Answer to your test is wrong. In this test the denominators of intermediate fractions (before reduction) exceed 2^64.

1/6265197409
Re: Test #9
Posted by bsu.mmf.team 6 Feb 2011 03:56
Oh, thanks, now I understood why it gets WA. Now my program gives correct answer to this test (I optimized it a little bit), but I found several tests with the same problem. It is interesting for me to solve it without BigInteger, I guess, there exists such solution for this problem.

After a lot of tries I gave up :(
AC now, but with big numbers.

Edited by author 07.02.2011 23:02
Re: Test #9
Posted by svr 27 Feb 2011 10:26
I got Wa22(ac 1-21) under positions:
r1*r2!=k*k-"irrational";(BUT IF i>min and i<MAX ONLY!)
else
1/sqrt(r)=a/sqrt(r1)+b/sqrt(r2);
a,b- recursion f(n,2i)=f(n-1,i),f(n,2i+1)=f(n-1,i)+f(n-1,i+1)
All- __int64
AC now:
a,b<=30- by induction.
int- is enought, nor __int64, nor BigInteger

Edited by author 27.02.2011 12:18
Re: Test #9
Posted by svr 27 Feb 2011 12:55
My mistake was: __int64 needed.
a+b<=2^30
Thank you a lot, svr!!!. I accepted with 0.015 s.
Posted by xurshid_n 21 Dec 2011 23:35
Re: Test #9
Posted by Toshpulatov (MSU Tashkent) 5 Feb 2020 22:58
Что бы не было переполнения вы могли сделать следующие : Представить r1 и r2 таким образом
r1 = A / B ^ 2
r2 = A / C ^ 2
Где А = r1 * r2 / gcd(r1, r2);
Отсюда найдете B и C.
Теперь в чем прелесть такого представления:
Вы наверное вывели формулу r3 = (r1 * r2 ) / (r1 + r2 + 2 * sqrt(r1, r2) );
Так вот если будете подставлять то получите r3 = A / ( B + C) ^ 2
т.е числитель не меняется а вот знаменатель будет меняться но не быстро !