Recovering a Fibonacci-type sequence
National Olympiad — Municipal round
Submission name: fibseq.cpp
Problem summary
A sequence obeys a[i]=a[i−1]+a[i−2] for i≥3. Given n, a[n], and a[n+1], recover a[1] and a[2].
Input
n a[n] a[n+1].
Output
a[1] a[2], separated by a space.
Constraints
1 ≤ n ≤ 30; the statement bounds sequence elements above by 2·10^9.
Worked example
An independently prepared example for this explanation.
Input
4 8 13
Output
2 3
Solution analysis
- Reverse the recurrence: a[i−1]=a[i+1]−a[i].
- Replace the known adjacent pair with the preceding adjacent pair n−1 times.
Why it works
Each reverse step is the unique pair consistent with the recurrence. After n−1 steps its indices are 1 and 2.
Complexity: O(n) time and O(1) space.
Watch out. n=1 needs no updates. Do not assume the sequence starts with 1,1.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each reverse step is the unique pair consistent with the recurrence. After n−1 steps its
// indices are 1 and 2.
#include<iostream>
#include<algorithm>
#include<utility>
#include<iterator>
using namespace std;
int main(){
int n;
long long a,b;
cin>>n>>a>>b;
while(--n){
long long prev=b-a;
b=a;
a=prev;
}
cout<<a<<' '<<b<<'\n';
}