Prepare the Diet
National Olympiad — National round
Submission name: diet.cpp
Problem summary
There are a, b and c carrots weighing 10, 20 and 30 grams. Each full day requires separate portions of 10, 30 and 20 grams, which may combine pieces. A cut can split 20 into 10+10, or 30 into 10+20; the resulting 20 may also be cut. Maximize the number of complete days, then minimize cuts. Unused stock is allowed.
Input
a b c.
Output
Maximum days, followed by the minimum cuts.
Constraints
Each stock count is nonnegative and below 1000000.
Worked example
An independently prepared example for this explanation.
Input
2 2 2
Output
2 0
Solution analysis
- Measure weights in tens of grams. The maximum day count D is total weight divided by 6, rounded down. Cutting everything to units proves this is achievable.
- Enumerate x carrots of size 3 to split. Keep up to D remaining size-3 carrots for lunches; let t be the number of lunches still needing size 3.
- Those t lunches and all D breakfasts need D+t units. A further y cuts of size-2 pieces produces two units each, so choose the smallest sufficient y. After reserving these units, D+t portions of size 2 remain; check their total available weight. Minimize x+y.
Why it works
For fixed x, use as many uncut size-3 carrots as possible. Every remaining size-3 lunch needs a unit plus a size-2 amount. Reserving these units leaves only size-2 portions, which can be formed from pairs of units or size-2 pieces. Thus the two checked inequalities are necessary and sufficient, and the minimum y is optimal for x.
Watch out. A portion may combine pieces. Do not demand one whole carrot of each size per day.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int main(){
long long a,b,c;
cin>>a>>b>>c;
long long d=(a+2*b+3*c)/6,ans=LLONG_MAX;
for(long long x=0;x<=c;x++){
// x splits of a size-3 carrot produce one unit and one size-2 piece.
long long t=max(0LL,d-(c-x)),ones=a+x,twos=b+x;
long long y=max(0LL,(d+t-ones+1)/2);
if(y<=twos&&ones+2*twos>=3*d+3*t){
ans=min(ans,x+y);
}
}
cout<<d<<' '<<ans<<'\n';
}