Hint

In what cases will operating on a digit decrease the number?

Answer

When the digit is larger than the one after it.

Hint

The earlier digits always make a bigger difference than the later ones.

Solution

Given ~K~ moves, Lookcook should move back the first ~K~ digits that are larger than the digit after it. These ~K~ digits can be found by keeping a monotonically nondecreasing stack. After finding these ~K~ values, move them in nondecreasing order (move the smallest of the ~K~ digits first and the largest last). This takes ~\mathcal O(n \log n)~ time for an ~n~ digit number.

Example

1
26451689
5

~6~ is bigger than ~4~. So ~6~ should be a digit that gets moved. The resulting number is ~2451689~.

~5~ is bigger than ~1~, so it should be moved. The resulting number is ~241689~.

Now that ~1~ is directly after ~4~, ~4~ should be moved. This leaves ~21689~.

Now that ~1~ is directly after ~2~, ~2~ should be moved. This leaves ~1689~.

~9~ is the last element. But we know that we will move ~2~ to the end, and it will be smaller than ~9~. So ~9~ should also be moved, leaving ~168~.

~8~ Should be moved for the same reason as ~9~, but we've used up all our ~5~ operations, so we stop now.

The ~K~ digits we've selected are ~\{6,5,4,2,9\}~. They should be moved in the non-decreasing order ~2,4,5,6,9~, giving the result as ~16824569~.