767. Emptying the Heaviest Bag

There are n bags, the i-th holding a[i] marbles. One OPERATION takes any single bag and divides its contents into two new bags, each holding at least one marble; you choose the split. You may perform at most ops operations in total, in any order, on any bags.

The penalty is the number of marbles in the fullest bag at the end. Print the smallest penalty achievable.

a = 9 4, ops = 2 answer 4 9 becomes 3+3+3, but the untouched 4 sets the penalty a = 10, ops = 4 answer 2 10 becomes five bags of 2 a = 7 2 5, ops = 0 answer 7 nothing may be split a = 8 8 8, ops = 3 answer 4 each 8 halves once, using all three operations

## Searching over plans is hopeless

An operation may be applied to a bag that was itself produced by an earlier operation, so the set of reachable configurations branches enormously. With ops as large as 10^9 there is nothing to enumerate.

Turn it around. Ask about the OUTCOME rather than the plan: can the penalty be held to m?

## Counting the operations a target needs

Bags never merge, so the bags at the end are a partition of each original bag independently. A bag of a[i] marbles that finishes as p bags cost exactly p - 1 operations, whatever order the splits happened in, because every operation raises the bag count by exactly one.

To finish with every bag at m or fewer, bag i must become at least ceil(a[i] / m) bags, and that many is always achievable: cut off m marbles at a time. So

cost(m) = sum over i of (ceil(a[i] / m) - 1) feasible(m) = cost(m) <= ops

## Why that count is optimal and not merely sufficient

Two halves of the claim.

It is ACHIEVABLE: splitting a bag of a[i] into ceil(a[i] / m) bags of size at most m is always possible, since ceil(a[i] / m) * m >= a[i], and the pieces can be made to hold at least one marble each because m >= 1.

It is NECESSARY: if bag i ends as p bags each holding at most m, then p * m >= a[i], so p >= a[i] / m, and since p is a whole number p >= ceil(a[i] / m). Fewer operations cannot get there.

Because the bags are independent, the total is the sum of the per-bag minimums. That is the whole proof, and it is worth noticing that the argument never mentions the ORDER of operations at all, which is exactly why the enormous search space collapses.

## Why the predicate is monotone

A plan that leaves every bag at m or below also leaves every bag at m + 1 or below, at no extra cost. So once a penalty is affordable, every larger penalty is affordable. The feasible values form a suffix and the answer is the FIRST true, which is the opposite direction from problems 764, 765 and 766.

## The bounds

lo = 1. A bag must hold at least one marble, so the penalty can never be driven below 1, and m = 0 would divide by zero.

hi = max(a), which is what you get by spending no operations at all. Always feasible, so the search can never run off the top.

## The boundary that breaks a careless implementation

Integer ceiling. Writing a[i] / m + 1 instead of (a[i] + m - 1) / m overcounts by one whenever m divides a[i] exactly. On a single bag of 10 with ops = 4 the correct answer is 2, because 10 becomes five bags of 2 at a cost of 4; the buggy ceiling prices that at 5 and settles on 3 instead. Use (a[i] + m - 1) / m, or -(-a[i] // m) in Python, and subtract 1 afterwards rather than folding the subtraction into the ceiling.

This searches for the FIRST true value, so the midpoint rounds DOWN and the update is hi = mid on success, not hi = mid - 1. That is the shape from #251 and #260, and swapping it with 764's shape gives an answer one too large.

## Overflow

This one is hygiene rather than a reachable failure, and the difference is worth naming, because the arithmetic looks dangerous and is not.

The ceiling (a[i] + m - 1) / m adds two values that each reach 10^9. But m never exceeds max(a), so the sum is at most 2 * 10^9 - 1 = 1999999999, and INT_MAX is 2147483647. It fits, with about seven percent to spare.

The running cost is bounded too, precisely because the loop stops the moment it passes ops. Up to that point the cost is at most ops <= 10^9, and the term that triggers the stop adds at most a[i] - 1 < 10^9, so the accumulator stays below 2 * 10^9. Sweeping the shapes the constraints allow, the largest value it actually reaches is 1999999998, on two bags of 10^9 with ops = 10^9.

Write both in 64-bit anyway. Each bound sits within seven percent of INT_MAX, and the second one depends entirely on the early break: remove the break and the cost at m = 1 becomes sum(a) - n, which reaches 2 * 10^14. Knowing which kind of warning you are reading is worth more than obeying it.

## Cost

Time O(n log(max a)). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ ops ≤ 10^9` - `1 ≤ a[i] ≤ 10^9`