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.
button presses are required just to confirm a length-
name, regardless of its letters (an A
button press upon selecting each letter, plus a final +
button press at the end). Therefore, if
, then no valid name exists. Otherwise, let
be the number of additional <
/>
button presses required.
Let's consider how many such button presses each letter in a name contributes. Let
be the number of button presses required to move the cursor to a letter
from the previous letter
(with the previous letter before the first one assumed to be A
). We'll either repeatedly press <
or >
, whichever requires fewer presses. These two options require
and
button presses (in some order), giving us
. We can observe that, given any previous letter
, it's possible to choose some next letter
such that
has any wanted value between
and
, inclusive.
We can then observe that a valid name exists if and only if
. Furthermore, we can construct a name for a given
value by greedily choosing letters one by one such that
is maximized each time (up to at most
), but without exceeding the remaining allotment of required button presses.
Comments