Maximum Number of Summands
National Olympiad — National round (2018 season)
Submission name: maxseq.cpp
Problem summary
Represent n as a sum using allowed positive values, with unlimited reuse. Maximize the number of summands, or report −1 when impossible.
Input
n k followed by k allowed values.
Output
The maximum summand count or −1.
Constraints
1 ≤ n < 100000; 1 ≤ k < 10; 1 ≤ allowed values < 10000.
Worked example
Input and output for the worked example discussed below.
Input
11 4 3 4 4 4
Output
3
Solution analysis
- Let best[s] be the maximum number of allowed summands with total s. Set best[0]=0 and use −1 for unreachable positive sums.
- Process sums in increasing order. If s−a is reachable for an allowed a≤s, append a and update best[s] with best[s−a]+1. Positive values ensure every predecessor sum is smaller.
- For n=11 and values 3,4, the construction 3+4+4 uses three terms. Repeating an allowed value is legal, while repeated copies of 4 in the input do not create new restrictions or improve the optimum.
Why it works
Every nonempty representation ends in some allowed summand, and removing it leaves one of the recurrence’s predecessor states; all appended reachable states are valid.
Complexity: O(nk) time and O(n) space, with one small set of transitions per sum.
Watch out. A greedy choice of the smallest value can leave an impossible remainder. Do not add one to an unreachable −1 state.
Commented C++17 solution
An independently written complete program with standard headers.
// Every nonempty representation ends in some allowed summand, and removing it leaves one of the recurrence’s
// predecessor states; all appended reachable states are valid..
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int target,count;
cin>>target>>count;
vector<int>allowed(count);
for(int&value:allowed){
cin>>value;
}
vector<int>best(target+1,-1);
best[0]=0;
for(int sum=1;sum<=target;sum++){
for(int value:allowed){
if(value<=sum&&best[sum-value]>=0){
best[sum]=max(best[sum],best[sum-value]+1);
}
}
}
cout<<best[target]<<'\n';
}