FIBPOS - Fibonacci Terms
The Fibonacci sequence is a sequence of integers in which each number is equal to the sum of the two preceding numbers. The first two integers in the sequence are both 1. Formally:
- F1 = 1
- F2 = 1
- Fi = Fi-1 + Fi-2 for each i > 2
The beginning of this sequence is 1, 1, 2, 3, 5, 8, 13, 21.
We'll define the Fibonacci position of an integer greater than or equal to 1 as follows:
- The Fibonacci position of 1 is 2 (since F2 = 1)
- The Fibonacci position of any integer n > 1 such that Fi = n is i
- The Fibonacci position of any integer n > 1 such that it is strictly between Fi and Fi+1 is i+(n-Fi)/(Fi+1-Fi) (informally, this means it is linearly distributed between Fi and Fi+1)
As examples, if FP(n) is the Fibonacci position of n,
- FP(1) = 2 (first rule)
- FP(5) = 5 (second rule F5 = 5)
- FP(4) = 4.5 (third rule, is right in the middle of F4 = 3 and F5 = 5)
Given an integer n, find its Fibonacci position as a double.
Input
First line contains T <= 10. The following N lines each contain an integer 1 <= n <= 108.
Output
For each test case, print the Fibonacci position of n, rounded to 6 places of decimal.
Example
Input: 4 1 5 4 100 Output: 2.000000 5.000000 4.500000 11.200000
Added by: | Mahesh Chandra Sharma |
Date: | 2011-01-28 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |