Muffins
Autumn Tournament (2014)
Submission name: muffins.cpp
Problem summary
Three kinds of muffins have given nonnegative prices and available quantities. Given a budget, buy the largest possible total number of muffins. Free muffins and unavailable kinds are allowed.
Input
Three prices, then three corresponding quantities, then the budget.
Output
The maximum number of muffins that can be bought.
Constraints
Every input integer is between 0 and 100000000000000000 inclusive.
Worked example
Original statement sample.
Input
5 3 8 2 6 4 23
Output
7
Solution analysis
- All muffins have the same benefit: each increases the count by one. Sort the three kinds by price, keeping each price paired with its stock. Buy from cheaper kinds first.
- For price zero, take the whole stock. Otherwise buy min(stock,budget/price), then subtract purchased·price. This multiplication is safe because purchased·price never exceeds the current budget; do not multiply the entire stock by the price. Use long long for all amounts.
- In the sample, buy six muffins costing 3 each, leaving 5. Then buy one costing 5. Seven muffins cost 23 and none of the remaining muffins is affordable.
Why it works
If a purchase includes an expensive muffin while a cheaper one remains available, replace it by the cheaper muffin. The count is unchanged and cost does not increase. Repeating yields an optimal purchase that exhausts cheaper stocks before buying dearer ones, exactly as the greedy algorithm does.
Watch out. Handle zero prices before division. The total count can be 3·10^17, so int is insufficient. Avoid stock·price overflow.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<utility>
using namespace std;
int main(){
array<pair<long long,long long>,3>kinds;
for(auto&kind:kinds){
cin>>kind.first;
}
for(auto&kind:kinds){
cin>>kind.second;
}
long long budget;
cin>>budget;
sort(kinds.begin(),kinds.end());
long long answer=0;
for(const auto&kind:kinds){
long long price=kind.first;
long long stock=kind.second;
long long take=stock;
if(price!=0){
take=min(stock,budget/price);
}
// This product is bounded by budget, even for huge stock.
budget-=take*price;
answer+=take;
}
cout<<answer<<'\n';
}