Fewest Rods
Autumn Tournament (2019)
Submission name: rods.cpp
Problem summary
There are b1, b2, b3 rods of lengths a1, a2, a3 centimetres. Place selected rods end to end to reach at least L centimetres. Find the fewest rods needed, or report that the stock is insufficient.
Input
Seven integers: a1 a2 a3 b1 b2 b3 L.
Output
The minimum number of rods, or 0 if reaching L is impossible.
Constraints
Every input integer is positive and smaller than 100.
Worked example
First official statement sample.
Input
1 1 1 1 1 1 5
Output
0
Solution analysis
- Sort the three rod types by decreasing length, keeping each length with its available count. Longer rods always contribute at least as much length for the same one-rod cost.
- Take rods in this order, stopping as soon as the accumulated length reaches L. If all rods are used without reaching L, output 0. At most 297 rods can be inspected.
- For 3 2 1 10 11 12 18, take six rods of length 3. They reach 18; any five rods have total length at most 15, so six is minimal.
Why it works
For any fixed count k, the k longest available rods have at least the total length of every other choice of k rods: replacing a shorter selected rod by a longer unselected one never decreases length. The algorithm takes exactly these prefixes. The first feasible prefix therefore has the smallest feasible count; if the full prefix fails, no choice can succeed.
Watch out. The target may be exceeded. Keep lengths paired with counts while sorting. Return 0 rather than a partial count when impossible.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For any fixed count k, the k longest available rods have at least the total length of
// every other choice of k rods: replacing a shorter selected rod by a longer unselected one never
// decreases length. The algorithm takes exactly these prefixes.
#include<algorithm>
#include<array>
#include<iostream>
#include<utility>
using namespace std;
int main(){
array<pair<int,int>,3>rods;
for(auto&rod:rods){
cin>>rod.first;
}
for(auto&rod:rods){
cin>>rod.second;
}
int target;
cin>>target;
sort(rods.rbegin(),rods.rend());
int length=0;
int count=0;
for(const auto&rod:rods){
for(int used=0;used<rod.second;++used){
length+=rod.first;
++count;
if(length>=target){
cout<<count<<'\n';
return 0;
}
}
}
cout<<0<<'\n';
}