UVa 10183

From Algorithmist
Jump to navigation Jump to search

10183 - How many Fibs?[edit]

Summary[edit]

A pretty ordinary BigNum problem.

Explanation[edit]

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

Gotcha's[edit]

The first number input may be 0. Note 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.

Notes[edit]

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.

Optimizations[edit]

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.

Solutions[edit]

Input[edit]

0 1
1 1
10 100
1234567890 9876543210
0 0

Output[edit]

1
1
5
4