Given X, compute the largest N such that FIB(N) < X.
Recall that:
The first line contains an integer X.
A single integer N.
| Input | Output |
|---|---|
| 10 | 6 |
| 35 | 9 |
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:
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)
#!/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)))