892. The Best Score From k Picks

n boxes hold given numbers of coins. You take exactly k turns, and each turn you must:

choose the box with the MOST coins add all of its coins to your score refill it with ceil(coins / 3) coins, rounded UP

Print the final score.

n = 3, k = 3, boxes 10 10 10 -> 30 n = 4, k = 2, boxes 1 10 3 3 -> 14 n = 3, k = 7, boxes 9 3 1 -> 19

Trace the second one. The most coins is 10, so the score is 10 and the box is refilled with ceil(10 / 3) = 4. The boxes are now 1 4 3 3, the most is 4, so the score is 14 and that box is refilled with ceil(4 / 3) = 2.

Note that k may exceed n, and since ceil(v / 3) is at least 1 for every v at least 1, no box ever empties. The third example takes seven turns from three boxes.

## Is taking the largest actually optimal?

There is nothing to prove, and that is worth saying plainly, because problems of this shape usually do need an exchange argument. Here the RULE says to take the box with the most coins. It is a simulation, not an optimisation, and the only question is how to run it quickly. Confusing the two wastes a lot of time on a proof that has no statement.

The ambiguity that does need settling is a tie: if two boxes hold the same maximum, either may be taken, and since they are equal the score and the resulting multiset are the same either way.

## What most people try first

Sorting once and walking down. After a box is taken it is refilled to about a third of its size, so it drops a long way down the order and something else is now the maximum. A single pass over sorted values takes 10 + 3 + 3 on the second example instead of 10 + 4.

Rescanning for the maximum each turn. Correct, O(n) per turn, and O(nk) overall, which is 4 * 10^10 at the limits.

## The method

build a max-heap of the box sizes score = 0 repeat k times: v = top of the heap score = score + v replace the top with ceil(v / 3) and sift down print score

Replacing the top and sifting down once is cheaper than a pop followed by a push, since it does one repair walk instead of two, and it is exactly what heapreplace does.

## Rounding up without floating point

ceil(v / 3) is (v + 2) / 3 in integer arithmetic for non-negative v. Do not write (int) ceil(v / 3.0): a double holds integers exactly only up to 2^53, which is 9007199254740992, and while 10^9 is far below that, the habit is what eventually breaks on a larger problem. The integer form has no such cliff.

Rounding DOWN instead would empty every box eventually and gives a different answer: on 9 3 1 with k = 7, rounding up gives 19 and rounding down gives a smaller total.

## Overflow, with the actual magnitude

The score is k values each up to 10^9, so it reaches 2 * 10^14. A signed 32-bit accumulator stops at 2147483647, and even the two-box test with k = 4 reaches 2666666668, which wraps to -1628300628.

The coin counts themselves are fine in 32 bits. The score is not.

## The boundary that breaks a careless implementation

k larger than n, which means boxes are revisited. A program that takes each box at most once answers the third example with 9 + 3 + 1 = 13 and then has nothing left to do.

The second one is a single box, where every turn takes the same box and the value shrinks geometrically.

## Related problems

Problem 878 runs the same max-heap loop with a different transform, halving instead of thirding, and asks HOW MANY turns are needed to reach a target rather than what the turns are worth. One counts operations, one accumulates a value, and the loop body is otherwise identical. Problem 877 is the min-heap mirror.

## Cost

Time O(n + k log n). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000` - `1 ≤ coins ≤ 1000000000`