Three Segment Lengths
National Olympiad — National round (2012 season)
Submission name: segments.cpp
Problem summary
Cut a length-n segment into exactly m pieces, each of length a, b or c. Count different triples of piece counts; their order along the segment is irrelevant.
Input
a b c m n.
Output
The number of nonnegative count triples.
Constraints
0<a<b<c<100; ma<n<mc; n<10^15.
Worked example
An independently prepared example for this explanation.
Input
2 7 9 20 100
Output
2
Solution analysis
- Let x,y,z count pieces of lengths a,b,c. Eliminate x=m−y−z to obtain Uy+Vz=D, where U=b−a, V=c−a and D=n−ma. If gcd(U,V) does not divide D, no solution exists.
- Choose the least nonnegative z0 satisfying Vz0≡D mod U, searching fewer than 100 residues. Set y0=(D−Vz0)/U. Every integer solution is z=z0+(U/g)t and y=y0−(V/g)t. Because 0≤z0<U/g, nonnegative z is equivalent to t≥0.
- Nonnegative y gives an upper bound on t; x=m−y−z gives a lower bound because V>U. Count the integers in the intersection. The sample triples are (8,12,0) and (10,5,5), hence 2. Large m and n do not require enumeration.
Why it works
After dividing by the gcd, the congruence has one residue class for z; the displayed parameterization is therefore all integer solutions. The three derived inequalities are exactly x,y,z≥0. Counting the integer parameter values in their intersection counts every valid triple once.
Watch out. Do not count permutations of pieces. Use 64-bit arithmetic. Handle a negative y0 before applying integer division, and round the lower bound upward.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
#include<algorithm>
// Algorithm: Let x,y,z count pieces of lengths a,b,c.
using namespace std;
int main(){
long long a,b,c,pieces,length;
cin>>a>>b>>c>>pieces>>length;
long long u=b-a;
long long v=c-a;
long long difference=length-pieces*a;
long long divisor=gcd(u,v);
if(difference%divisor!=0){
cout<<0<<'\n';
return 0;
}
long long stepZ=u/divisor;
long long stepY=v/divisor;
long long z=0;
while((difference-v*z)%u!=0){
z++;
}
long long y=(difference-v*z)/u;
if(y<0){
cout<<0<<'\n';
return 0;
}
long long upper=y/stepY;
long long lower=0;
long long excess=y+z-pieces;
if(excess>0){
long long gain=stepY-stepZ;
lower=(excess+gain-1)/gain;
}
cout<<max(0LL,upper-lower+1)<<'\n';
}