Balancing three film genres
National Olympiad — Municipal round
Submission name: cowboys.cpp
Problem summary
There are a,b,c films in three genres and a budget n. Any film can be sold for 1; a new film of any genre costs 2. Before screenings begin, make the three genre counts equal. Maximize that common count: one new film of each genre is shown per evening.
Input
a, b, c, n, separated by whitespace.
Output
Maximum possible evenings.
Constraints
0≤a,b,c≤10^9; 0≤n≤10^15.
Worked example
An independently prepared example for this explanation.
Input
1 4 7 3
Output
4
Solution analysis
- For a target x, sell each surplus film and buy each deficit film. Its net cost is sum(2·max(0,x−a[i])−max(0,a[i]−x)).
- This cost increases with x. Binary-search the largest affordable target.
Why it works
At a fixed target, keeping available films and selling only surplus is cheapest; selling and repurchasing a kept film loses money. Thus the cost test is necessary and sufficient, and monotonicity validates binary search.
Watch out. Sale and purchase prices differ. All transactions occur before the first evening.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: At a fixed target, keeping available films and selling only surplus is cheapest; selling
// and repurchasing a kept film loses money. Thus the cost test is necessary and sufficient, and
// monotonicity validates binary search.
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
long long a[3],n;
cin>>a[0]>>a[1]>>a[2]>>n;
long long lo=0,hi=n+a[0]+a[1]+a[2]+1;
while(lo+1<hi){
long long x=(lo+hi)/2,cost=0;
for(long long v:a){
cost+=x>v?2*(x-v):x-v;
}
if(cost<=n){
lo=x;
}
else{
hi=x;
}
}
cout<<lo<<'\n';
}