FibonacciPositioning
SRM 298 · 2006-04-11 · by soul-net
SRM 298 · 2006-04-11 · by soul-net · Search, Simple Math, Sorting
Problem Statement
Problem Statement
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:
We'll define the fibonacci position of an integer greater than or equal to 1 as follows:
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, return its fibonacci position as adouble .
- F1 = 1
- F2 = 1
- Fi = Fi-1 + Fi-2 for each i > 2
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)
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, return its fibonacci position as a
Notes
- The returned value must be accurate to 1e-9 relative or absolute.
Constraints
- n will be between 1 and 100000000 (108), inclusive.
Examples
0)
1 Returns: 2.0
1)
2 Returns: 3.0
2)
3 Returns: 4.0
3)
5 Returns: 5.0
4)
4 Returns: 4.5
Examples from the problem statement.
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FibonacciPositioning with a public method double getFPosition(int n) · 123 test cases · 2 s / 256 MB per case