Flip Flops

The Useful Kind of Violence

If a monster is never killed, throwing flip flops at it is useless: it consumes $1$ flip flop and increases that monster's power by $1$, making it harder to kill. So every useful flip flop must be thrown at a monster that will eventually die.

Now suppose the current combat power is $c$, we have $k$ flip flops left, and we decide to kill a monster with initial power $a \le c$ right now.

Before killing it, we may throw $x$ flip flops at it, but it must remain killable:

$$0 \le x \le c-a.$$

Also $x \le k$. Therefore the maximum legal choice is

$$x=\min(k,c-a).$$

Using fewer is never better. One extra flip flop used now decreases $k$ by $1$ but increases the resulting $c$ by $1$. The total resource $c+k$ stays the same, while current combat power gets larger. Larger current power can only help. So if we kill a monster now, we should pump it as much as possible before killing it.

Compressing the State

Let

$$S=c+k.$$

After killing a chosen monster $a$ with the maximum possible number of flip flops,

$$S' = S+a,$$

because killing adds the monster's original power $a$, and thrown flip flops merely move value from $k$ into $c$.

The new combat power is

$$c'=c+a+\min(k,c-a).$$

Since $k=S-c$, this becomes

$$c'=\min(S+a,2c)=\min(S',2c).$$

This formula is the whole problem wearing a fake mustache.

Which Monster Should Die First?

Among all currently killable monsters, choose the one with maximum $a$.

Why? For fixed current $(c,S)$, killing a larger $a$ gives a larger

$$S'=S+a,$$

and therefore also a larger or equal

$$c'=\min(S+a,2c).$$

So the strongest killable monster gives the best next state. Smaller killable monsters are not going anywhere: since $c$ never decreases, if $a_i \le c$ now, then it will remain killable later.

A clean exchange argument seals it. Suppose an optimal strategy first kills some killable monster $q$, but there is another killable monster $m$ with $m \ge q$. Kill $m$ first instead. The resulting state dominates the original one: it has at least as much current combat power $c$ and at least as much total resource $S=c+k$. Then follow the old strategy; when it would have killed $m$, kill $q$ instead. Since $q$ was killable from the start, it is still killable. The strategy is no worse. So taking the largest killable monster is safe.

Algorithm

Repeat:

1. Find an alive monster with maximum $a_i$ such that $a_i \le c$.
2. If no such monster exists, stop. Throwing at unkillable monsters only increases their power, so it cannot unlock anything.
3. Let $$x=\min(k,c-a_i).$$
4. Throw $x$ flip flops, kill the monster, and update $$c \leftarrow c+a_i+x,\qquad k \leftarrow k-x.$$

There are only $n \le 100$ monsters, so a simple linear scan each step is more than enough.

Complexity

For each test case, we do at most $n$ iterations, and each iteration scans $n$ monsters.

$$O(n^2)$$

time and

$$O(n)$$

memory. Use 64-bit integers: the answer can exceed $10^9$, as the sample politely screams at you.