The Fewest Calculator Entries
National Olympiad — Regional round (2011 season)
Submission name: calc.cpp
Problem summary
A calculator evaluates operations sequentially from left to right. Each entered number is between 1 and n; after the first entry you may add or multiply the current result by the next entry. Find the fewest entered numbers needed to obtain s.
Input
Two integers s and n, in that order.
Output
The minimum number of entered numbers.
Constraints
1 ≤ n < 100; 1 ≤ s < 1000000.
Worked example
An independently prepared example for this explanation.
Input
51 3
Output
5
Solution analysis
- Every useful operation increases the current positive result: multiplication by 1 can be omitted. Hence all intermediate results in an optimal computation lie between 1 and s. Process them in increasing order, with best[value] equal to the minimum entries needed to reach value.
- A first entry between 1 and n costs one. Reaching value by addition costs 1 plus the smallest best[previous] with previous between value−n and value−1. Maintain this sliding-window minimum in an increasing deque of best values; expired indices leave the front.
- After best[value] is final, propagate multiplication transitions to value·2, value·3, …, value·n, stopping before s is exceeded. Those targets are larger, so they will be processed later and already contain any multiplication candidates.
- For s=51,n=3, enter 3, add 2 to get 5, multiply by 3 to get 15, add 2 to get 17, then multiply by 3 to get 51. This uses five entries. The DP also checks all shorter ways, proving none uses four.
Why it works
At value, every addition predecessor is a smaller integer in the maintained window. Every multiplication predecessor is also smaller and has already propagated its optimal cost. Together with the possible one-entry initialization, these exhaust the last-step possibilities. The deque keeps exactly the minimum cost among eligible addition predecessors; removing a worse older index is safe because the newer cheaper index expires no earlier. Induction gives every finalized value its optimal entry count.
Watch out. The input order is s then n. A multiplication has no ordinary operator-precedence effect: it acts on the entire current result. Do not include multiplication by 1 as a useful transition. Expire deque indices before querying and only append a value after its cost is finalized.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int target,largestEntry;
cin>>target>>largestEntry;
vector<int>best(target+1,target+1);
deque<int>minimum;
for(int value=1;value<=target;++value){
while(!minimum.empty()&&minimum.front()<value-largestEntry){
minimum.pop_front();
}
if(value<=largestEntry){
best[value]=1;
}
if(!minimum.empty()){
best[value]=min(best[value],best[minimum.front()]+1);
}
// Only larger targets receive multiplication candidates.
for(int factor=2;factor<=largestEntry&&factor<=target/value;++factor){
best[value*factor]=min(best[value*factor],best[value]+1);
}
while(!minimum.empty()&&best[minimum.back()]>=best[value]){
minimum.pop_back();
}
minimum.push_back(value);
}
cout<<best[target]<<'\n';
}