Thrifty Shopper
Autumn Tournament (2007)
Submission name: saver.cpp
Problem summary
Buy at least N tissue packets as cheaply as possible. One packet costs 12 stotinki, a stack of 8 costs 82, and a box of 40 stacks (320 packets) costs 3050. Buying surplus packets is allowed. Output the purchased box, stack, and individual-packet counts.
Source clarification. Buying at least N rather than exactly N is confirmed by the original sample N = 310, whose output buys one 320-packet box.
Input
One integer N.
Output
Three nonnegative integers: boxes, stacks, individual packets in a minimum-cost purchase.
Constraints
0 < N < 1000000.
Worked example
Original statement sample.
Input
310
Output
1 0 0
Solution analysis
- Work in stotinki to avoid rounding. Enumerate the number of boxes from zero through ceil(N/320); more boxes can only add unnecessary cost.
- For a fixed box count, let remaining = max(0, N − 320 × boxes). Consider floor(remaining/8) stacks with the leftover individual packets, and also one extra stack with no individuals. More extra stacks cannot help; one fewer stack replaces at most eight packets and costs more.
- For N = 310, 38 stacks and 6 packets cost 3188, while 39 stacks cost 3198. One box costs 3050 and supplies 320 packets, so the sample answer is 1 0 0.
Why it works
An optimum never needs more than ceil(N/320) boxes, since those boxes alone already suffice. Fix any enumerated box count. If fewer than floor(remaining/8) stacks are used, adding a stack replaces eight individual packets and reduces cost by 96 − 82 = 14. Thus only the floor stack count and the next count can be optimal; any larger count is surplus with extra cost. The enumeration examines the best purchase for every possible box count and selects a global minimum.
Watch out. A box contains 320 packets, not 40. Exact fulfillment is not required, as the original 310-packet sample demonstrates. Keep monetary calculations in integer stotinki.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: An optimum never needs more than ceil(N/320) boxes, since those boxes alone already
// suffice. Fix any enumerated box count.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int needed;
cin>>needed;
long long bestCost=numeric_limits<long long>::max();
int bestBoxes=0,bestStacks=0,bestSingles=0;
for(int boxes=0;boxes<=(needed+319)/320;boxes++){
int remaining=max(0,needed-320*boxes);
int fullStacks=remaining/8;
for(int extra=0;extra<=1;extra++){
int stacks=fullStacks+extra;
int singles=max(0,remaining-8*stacks);
long long cost=3050LL*boxes+82LL*stacks+12LL*singles;
if(cost<bestCost){
bestCost=cost;
bestBoxes=boxes;
bestStacks=stacks;
bestSingles=singles;
}
}
}
cout<<bestBoxes<<' '<<bestStacks<<' '<<bestSingles<<'\n';
}