Proficient.
Put your skills to the test.

Problem summary

There are A adventure films, B action films and C comedies, plus N units of money. A film of any genre costs 2 to buy and can be sold for 1. All trades happen before screenings start. Find the maximum number of evenings with one new film of each genre per evening.

Constraints

0 ≤ A,B,C ≤ 10⁹; 0 ≤ N ≤ 10¹⁵.

Worked example

An independently prepared example for this explanation.

3
7
4
10

6

Solution analysis

1. For a proposed number x of evenings, keep x films of each genre. Each missing film costs 2, while each surplus film can be sold for 1. Thus the minimum net expense is the sum of 2·max(0,x−stock)−max(0,stock−x) over the three genres.
2. The target is feasible exactly when this expense is at most N: sell every surplus first, then buy the deficits. As x increases, each genre’s contribution increases with slope one below its stock and two above it. Feasibility is therefore monotone, allowing integer binary search.
3. In the example a target of six needs three adventure films and two comedies, costing 10, while selling one action film earns 1. The expense 9 fits the budget 10. Seven evenings would cost 14 and cannot be funded. An exclusive upper bound is (A+B+C+N)/3+1, since selling loses no units of the combined film-plus-money total and buying decreases it.

Why it works

For a fixed target it never helps to sell a film of a genre still below target, nor to retain surplus films while lacking money. Keeping the required films, selling surpluses and buying deficits therefore achieves the minimum expense in the formula. Its monotonicity makes binary search return exactly the largest feasible target.

Watch out. A sale earns 1 but a purchase costs 2. Negative net expense is feasible. Use 64-bit arithmetic for the budget, bounds and costs.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<iostream>
// Algorithm: For a proposed number x of evenings, keep x films of each genre.
using namespace std;
int main(){
    array<long long,3>stock;
    long long budget;
    cin>>stock[0]>>stock[1]>>stock[2]>>budget;
    long long low=0;
    long long high=(stock[0]+stock[1]+stock[2]+budget)/3+1;
    while(high-low>1){
        long long middle=(low+high)/2;
        long long expense=0;
        for(long long count:stock){
            expense+=2*max(0LL,middle-count)-max(0LL,count-middle);
        }
        if(expense<=budget){
            low=middle;
        }
        else{
            high=middle;
        }
    }
    cout<<low<<'\n';
}