Minimum Function Applications
National Olympiad — National round
Submission name: functions.cpp
Problem summary
Starting from zero, repeatedly add one of K distinct positive increments. For each target N, find the fewest additions needed to reach it exactly. Each increment can be reused without limit.
Input
K; K increments; Q; then Q target values.
Output
One minimum per query; 0 when the positive target is unreachable.
Constraints
2 ≤ K ≤ 10; 1 ≤ increments ≤ 1000; 1 ≤ N ≤ 1000000; 1 ≤ Q ≤ 100000.
Worked example
An independently prepared example for this explanation.
Input
2 3 5 3 9 10 1
Output
3 2 0
Solution analysis
- Read all queries and compute up to their maximum.
- Set dp[0]=0 and other states to infinity. For each sum s try every increment a≤s, taking dp[s−a]+1.
- Positive increments ensure predecessors are already solved.
Why it works
Every construction has a final increment a; removing it leaves a construction of s−a. Minimizing over the last increment is both necessary and sufficient.
Watch out. Greedy selection of the largest increment is not generally optimal.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every construction has a final increment a; removing it leaves a construction of s−a.
// Minimizing over the last increment is both necessary and sufficient.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin>>k;
vector<int>a(k);
for(int&x:a){
cin>>x;
}
int q;
cin>>q;
vector<int>v(q);
int mx=0;
for(int&x:v){
cin>>x;
mx=max(mx,x);
}
const int INF=1000000000;
vector<int>d(mx+1,INF);
d[0]=0;
for(int s=1;s<=mx;s++){
for(int x:a){
if(x<=s){
d[s]=min(d[s],d[s-x]+1);
}
}
}
for(int x:v){
cout<<(d[x]==INF?0:d[x])<<'\n';
}
}