|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Test #9 | bsu.mmf.team | 1812. The Island of Bad Luck 2 | 5 Feb 2020 22:58 | 7 | Test #9 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 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.
My AC program answer:
1/6265197409 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 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
т.е числитель не меняется а вот знаменатель будет меняться но не быстро ! 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 My mistake was: __int64 needed.
a+b<=2^30 | | help on #11 | 侑子小姐 | 1812. The Island of Bad Luck 2 | 6 Jul 2012 21:38 | 2 | 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. All right...I make a mistake....-_____- | | Irreducable fraction | LSBG | 1812. The Island of Bad Luck 2 | 30 Jan 2011 16:38 | 2 | Hello what should I print if the answer is integer, say 1:
1/1
or
1
?
Thank you. After many trials it turned out it should be printed as 1/1. |
|
|
|
