Hints: Flip Flops

You can kill monsters in any order, but throwing flip flops only increases a monster’s power. Before you kill a monster, you may spend flip flops to raise its $a_i$ (each flip flop adds $1$), but you can never raise it above your current combat power $c$ plus the sum of powers you have already absorbed from killed monsters.

What invariant suggests sorting the monsters by $a_i$ before simulating?

Answer to Hint 1: Sort by nondecreasing $a_i$. If you ever kill a monster with value $x$, every monster you kill later must have had original $a_i \le x$ at the moment you could first reach it; processing smaller $a_i$ first never blocks a monster that could have been killed later in some other order (exchange argument / greedy).

Answer to Hint 2: After sorting, process monsters one by one. Let sum be the total $a$ you have already gained from kills (so your power before the next kill is $c + \text{sum}$). For the next monster with current value $a_i$, you may raise it to any $x \in [a_i,, \min(c+\text{sum},, a_i+k)]$ using $x-a_i$ flip flops, then add $x$ to sum and continue.

Why can you stop the first time $a_i > c + \text{sum}$ (before spending flips on that monster)?

Answer to Hint 3: All remaining monsters have $a_i$ at least as large as the current one (sorted order). If even the raw $a_i$ already exceeds your reachable power $c+\text{sum}$, you can never kill this monster or any later one, so you break out of the loop.

Answer to Hint 4: Implementation: sort a; maintain sum and remaining k. For each a[i], let upper = c + sum. If a[i] > upper, break. Otherwise set x = min(upper, a[i] + k), subtract x - a[i] from k, add x to sum. Print c + sum.