Hey guys,
So there is this problem on acmp.ru that asks you to determine if a given number N
is a fibonacci number where $$$ 1<= N <= 10^{100000}$$$.
Time: 8 sec. Memory: 16 MB
I tried to solve this with this bigint in c++ using brute force approach. But it gave TLE on test 14. Then I switched to python, did the same thing, and got AC. After some googling, I also found that a number N
is a fibonacci number if $$$ 5*N^2+4 $$$ or $$$ 5*N^2-4 $$$ is a perfect square. So i tried it with python but it got WA on test 3, probably because of some precision errors.
Here are my attempts:
Attempt 1 (TLE on test 14)
#include "bits/stdc++.h" using namespace std; int main(){ string r = "", line; ifstream inp; ofstream outp; inp.open ("INPUT.txt"); outp.open ("OUTPUT.txt"); getline (inp, line); bigint x = line, a = 0, b = 1, tmp; while(a < x){ tmp = b; b = a+b; a = tmp; } if(a == x) r = "YES\n"; else r = "NO\n"; outp << r; inp.close(); outp.close(); }
I didnt include some stuff like bigint struct, because code would be like 400/500 lines long with it.
Attempt 2(AC)
from math import sqrt with open("INPUT.TXT") as inp: r=''; x=int(next(inp)); a, b = 0, 1; while(a < x): a, b = b, a + b; if(a == x): r = 'YES'; else: r = 'NO'; with open("OUTPUT.TXT", 'w') as out: out.write(r);
Attempt 3( WA on test 3)
from math import sqrt with open("INPUT.TXT") as inp: r = ''; x = int(next(inp)); n = 5*x**2; sq1 = int(sqrt(n+4)); sq2 = int(sqrt(n-4)); if(sq1*sq1 == n+4 or sq2*sq2 == n-4): r = "YES"; else: r = "NO"; with open("OUTPUT.TXT", 'w') as out: out.write(r);
So, I'm wondering how we could get AC with python for this problem, and if its possible to fix the precision error of this second approach.