|
|
вернуться в форумTest #9 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 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 Re: Test #9 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 Послано svr 27 фев 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 Послано svr 27 фев 2011 12:55 My mistake was: __int64 needed. a+b<=2^30 Thank you a lot, svr!!!. I accepted with 0.015 s. Re: Test #9 Что бы не было переполнения вы могли сделать следующие : Представить 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 т.е числитель не меняется а вот знаменатель будет меняться но не быстро ! |
|
|