Fibonacci-Prefix Stick Partitions
National Olympiad — National round (2022 season)
Submission name: sec.cpp
Problem summary
Count partitions of M into L distinct positive lengths, with no three forming a triangle; the first L−2 sorted lengths are consecutive entries of1,2,3,5,8,… .
Input
M L.
Output
The partition count.
Constraints
6≤M≤10^9; 3≤L≤35.
Worked example
Input and output for the worked example discussed below.
Input
14 3
Output
9
Solution analysis
- Enumerate the fixed Fibonacci prefix’s starting point. Let its sum be S, its final term b, and preceding term a when present.
- For the remaining x<y, let T=M−S. Require x≥b+1 and, when a exists, x≥a+b. The last triple requires y=T−x≥b+x, hence x≤floor((T−b)/2). Count integers in this interval.
- For14,3, prefixes1,2,3 allow respectively5,3,1 choices, giving9. Consecutive Fibonacci terms already satisfy the nontriangle condition by equality.
Why it works
An increasing sequence has no triangular triple exactly when each term is at least the sum of its two predecessors. The prefix satisfies this, and the stated x and y bounds enforce the final two cases. Each sorted partition has one unique prefix and x.
Watch out. Degenerate triangles are allowed. Use only one initial1; when L=3 the prefix has no predecessor a.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// An increasing sequence has no triangular triple exactly when each term is at least the sum of its two
// predecessors.
int main(){
long long total;
int parts;
cin>>total>>parts;
vector<long long>f={1,2};
while(f.back()<=total){
f.push_back(f.back()+f[f.size()-2]);
}
int length=parts-2;
long long answer=0;
for(int start=0;start+length<=int(f.size());start++){
long long sum=0;
for(int i=0;i<length;i++){
sum+=f[start+i];
}
long long last=f[start+length-1];
long long lower=last+1;
if(length>=2){
lower=max(lower,last+f[start+length-2]);
}
long long remaining=total-sum;
if(remaining<last){
continue;
}
long long upper=(remaining-last)/2;
if(upper>=lower){
answer+=upper-lower+1;
}
}
cout<<answer<<'\n';
}