Nonconsecutive Fibonacci Representation
National Olympiad — National round (2013 season)
Submission name: pres.cpp
Problem summary
Represent n as a sum of distinct numbers from 1,2,3,5,8,…, without selecting consecutive sequence terms. Print increasing summands.
Input
One integer n.
Output
Summands joined by + without spaces.
Constraints
0 < n < 10^9; every input has a valid representation.
Worked example
Input and output for the worked example discussed below.
Input
17
Output
1+3+13
Solution analysis
- Generate the sequence beginning 1,2 until it passes n. Inspect terms largest first; whenever a term fits the remainder, select it and subtract it.
- After choosing F[k], the remainder is smaller than F[k−1], because the previous remainder was below F[k+1]=F[k]+F[k−1]. This automatically forbids the consecutive predecessor.
- For 17 take 13, leaving 4; then take 3 and 1. Reverse the selected list to print 1+3+13. No subset search is needed, and the term 1 ensures the remainder can finish at zero.
Why it works
At each step the largest fitting term leaves a nonnegative remainder below its predecessor. Thus selected terms are distinct and nonconsecutive. Repeated subtraction decreases the remainder until zero, establishing a valid exact sum.
Watch out. Start 1,2 rather than duplicate ones. Print increasing values and no leading or trailing plus sign.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int remaining;
cin>>remaining;
vector<int>fibonacci{1,2};
while(fibonacci.back()<=remaining){
fibonacci.push_back(fibonacci.back()+fibonacci[fibonacci.size()-2]);
}
vector<int>selected;
// The greedy remainder is too small to select the preceding term.
for(int i=int(fibonacci.size())-1;i>=0;i--){
if(fibonacci[i]<=remaining){
selected.push_back(fibonacci[i]);
remaining-=fibonacci[i];
}
}
reverse(selected.begin(),selected.end());
for(size_t i=0;i<selected.size();i++){
if(i>0){
cout<<'+';
}
cout<<selected[i];
}
cout<<'\n';
}