Sort 12 Discussions, By:
Please Login in order to post a comment
This problem is trivial. No need for the use of fractions. Just feed a, b with a function returning a + b + b, a + b, and begin with 1, 1. Compare the len of str(a) and str(b). Done. Took less than a minute.
a + b + b, a + b
"Each fraction is built from the one before by a simple rule: add top and bottom to get new bottom, add top and twice bottom to get new top. That sequence converges to the square root of 2." --- John Derbyshire, Prime Obsession
(Note that you'll have to modify this procedure slightly if you don't store each old bottom, or denominator, when replacing it with the next one.)
Is there any limitation on memory? I can pass my test in my own computer. but test #4 and #5 get wrong answer there. Thanks a lot.
Were you able to sort out the problem. My code is also showing wrong answer for test #4 and #5. Any suggestions would be helpful. Thanks!!
All testcases showing success but 4th and 5th test cases terminated due to timeout.
If anyone is having issues with case 7, remember to consider that n includes iteration n itself.
from fractions import Fraction
n = int(input().strip())
dec = [0,Fraction(1,2)]
for i in range(2,n+1):
temp1 = Fraction(1,2+dec[i-1])
temp2 = Fraction(1,1)
temp3 = temp2+temp1
nume = temp3.numerator
deno = temp3.denominator
if len(str(nume))>len(str(deno)): print(i)
It seems a little easy, attached codes for your kind reference.
I'm using F# and BigIntegers for this problem. Initially got a TLE on test case 4 and 5. Locally for n=10^4 my solution would run for about 8 seconds. So to get my solution accepted, I precalculated everything and used that. But that's not very satisfying.
Did anybody solve this problem in a .NET language or Java, without precalculation? Did I miss any cleverness to avoid using BigIntegers and huge numbers? Any hint would be appreciated. Thanks!
I did it with BigInteger through Scala's BigInt wrapper.
What I did to get TLEs from cases 4 and 5 was to convert the BigInteger into a string, forcing calculation for all the digits, rather than only calculating the number of digits. It's only necessary to find a sufficiently accurate base-10 logarithm for the BigInteger.
It seems very easy to solve using "fractions" class of python and yes it is! but I am getting TLE for TC 4 and 5.......any suggestions to optimize it? Thank You!
Has some done this in c also ?
Please let me know as I am able to pass testcases 1 ,6,7 but not others ?
Yes, a lot of people had done it in C.
Best of luck!
I'm having the same problem. Passing only 1, 6, 7. What did you do?
Can anybody help me how to add two numbers that are stored in strings and assign the result to another string ?
Why not integer array?
meanwhile pick a language where you can deal with BIgInteger :)