There are a few different rounding methods. The most common one rounds up/down from 5. Another one rounds up/down depending on the number being even or odd (this has to do with statistical bias). Here we'll implement a yet another type of rounding -- rounding a number to the closest whole integer in the Fibonacci sequence. If two elements in the sequence are equally far away, round up.

The Fibonacci sequence is defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)

Which produces a sequence of: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The input file DATA2.txt will contain 5 lines, integers 0 <= N <= 1,000,000,000.

The output file OUT2.txt will contain 5 lines, each a corresponding integer rounded to the closest number from the fibonacci sequence.

1
2
4
22
1000000000
		        

1
2
5
21
1134903170