Solution of Fib

This problem is simple in theory, but the actual implementation makes it a bit trickier. Due to the constraints, some Fibonacci values may just barely exceed the maximum value that can be stored on a 64-bit numeric data type. The following implementation works as intended:

long long a = 0, b = 1;
while(a < x - b) {
    long long c = a + b;
    a = b;
    b = c;
    ++n;
}

Whereas this very similar piece of code fails the test cases:

long long a = 0, b = 1;
while(a + b < x) {
    long long c = a + b;
    a = b;
    b = c;
    ++n;
}

This overflow problem can be avoided altogether by using a language which provides large numeric data types:

Haskell implementation:

main = do
    input <- getContents
    let xs = map read (words $ last $ lines input) :: [Integer]

    putStrLn $ unwords $ map (show . solve) xs
        where solve x = length $ takeWhile (< x) fibos
              fibos = 1:1:zipWith (+) fibos (tail fibos)

Python implementation:

#!/usr/bin/python3

n = int(input())

ans = []
for x in map(int, input().split()):
    fibos = [0, 1]
    while fibos[-1] < x:
        fibos.append(fibos[-1] + fibos[-2])
    ans.append(len(fibos) - 2)

print(" ".join(map(str, ans)))