| ENG RUS | Timus Online Judge |
Discussion of Problem 1812. The Island of Bad Luck 2bsu.mmf.team Test #9 [6] // Problem 1812. The Island of Bad Luck 2 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 Alipov Vyacheslav [Tomsk PU] Re: Test #9 [2] // Problem 1812. The Island of Bad Luck 2 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. My AC program answer: 1/6265197409 bsu.mmf.team Re: Test #9 [1] // Problem 1812. The Island of Bad Luck 2 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 Toshpulatov (MSU Tashkent) Re: Test #9 // Problem 1812. The Island of Bad Luck 2 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 т.е числитель не меняется а вот знаменатель будет меняться но не быстро ! svr Re: Test #9 [2] // Problem 1812. The Island of Bad Luck 2 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 svr Re: Test #9 // Problem 1812. The Island of Bad Luck 2 27 Feb 2011 12:55 My mistake was: __int64 needed. a+b<=2^30 xurshid_n Thank you a lot, svr!!!. I accepted with 0.015 s. // Problem 1812. The Island of Bad Luck 2 21 Dec 2011 23:35 侑子小姐 help on #11 [1] // Problem 1812. The Island of Bad Luck 2 6 Jul 2012 21:05 I got about 20 WAs on #11, can anyone tell me any trick on this test? I didn't use biginteger, I checked every * operator, and I'm sure it wasn't overflow. 侑子小姐 Re: help on #11 // Problem 1812. The Island of Bad Luck 2 6 Jul 2012 21:38 All right...I make a mistake....-_____- LSBG Irreducable fraction [1] // Problem 1812. The Island of Bad Luck 2 30 Jan 2011 16:24 Hello what should I print if the answer is integer, say 1: 1/1 or 1 ? Thank you. LSBG Re: Irreducable fraction // Problem 1812. The Island of Bad Luck 2 30 Jan 2011 16:38 After many trials it turned out it should be printed as 1/1.
|