UVa 10183

From Algorithmist

Contents 1 10183 - How many Fibs? 2 Summary 3 Explanation 4 Gotcha's 5 Notes 6 Optimizations 7 Input 8 Output

[edit] 10183 - How many Fibs?

• http://acm.uva.es/p/v101/10183.html

[edit] Summary

A pretty ordinary BigNum problem.

[edit] Explanation

Generate the Fibonacci sequence until the last number generated exceeds 10¹⁰⁰ and store it an array. It ends up taking about 480 numbers.

[edit] Gotcha's

The first number input may be 0. Not that that the problem defines a fairly non-standard sequence, where the first two numbers in the sequence aren't both 1, but rather 1 and 2.

[edit] Notes

The Fibonacci numbers increase by approximately a factor of . Thus, there are O(d) Fibonacci numbers with less than or equal to d digits. The exact constant multiple hidden by the O is . This would predict that we would need 478 numbers to store the Fibonacci numbers with less than 100 digits, when we actually used 480.

[edit] Optimizations

Since we never have to through more than 500 numbers, and the size of the numbers, about 100 digits, is near the size of the sequence itself, a linear search or two find the correct lower and upper indices in the sequence is sufficient to pass the time limit. However, a binary search will yield a lower time.

[edit] Input

0 1
1 1
10 100
1234567890 9876543210
0 0

[edit] Output

1
1
5
4