## Editorial for An Animal Contest 4 P1 - Dasher's Digits

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ThingExplainer

Due to the cyclic nature of the algorithm, it suffices to simulate the algorithm until we encounter the 0 at the front of the string, at which point it can be removed and the remaining characters outputted in order.

Time Complexity:

If , note that we care only about the 0 that is removed last. This can be done by comparing values, breaking ties by comparing the indices at which the 0's appear in the input string. We can then remove the 0 that is removed first without any consequence.

From this point onwards, we can perform the same sort of simulation as outlined in Subtask 1.

Time Complexity:

We still only care about the last 0 that is removed. We can find the index of this 0 by sorting the 0's based on their value and breaking ties by selecting the 0 that is further back. Let's call the index of this last 0 . We now separate the number into two strings and , where contains all non-0 characters in the input order before , and contains all the non-0 characters in the input order after . When we reach for the last time, the string can be shown to be , where represents concatenation.