Ваша задача – преобразовать строку MI в строку MU, при этом пользуясь такими правилами:
- Если последняя буква в строке I, вы можете добавить после нее U. Например: MI => MIU.
- Часть строки, которая следует за буквой M, можно удвоить, т.е. Mx превратить в Mxx. Например: MIU => MIUIU.
- Последовательность III можно изменить на U. Например: MUIIIU => MUUU.
- Последовательность UU можно удалить. Например: MUUU => MU.
Решение
Соблюдая указанные 4 правила, строку MI в строку MU превратить невозможно.
Почему?
Давайте проанализируем правила. Первым делом бросается в глаза тот факт, что в строке в любом случае будет только одна буква M: она дается нам в изначальной строке MI. Зафиксируем этот момент и идем дальше.
Теперь обозначим символом n число повторений буквы I.
В первой строке MI только одна буква I, значит n = 1. Единица на три не делится. Изменение значения n предусмотрено только правилами 2 и 3 (по которым n можно либо удвоить, либо уменьшить на три). Обе эти операции никогда не дадут нам n, значение которой можно было бы без остатка разделить на 3, если изначально, до преобразований, оно на 3 не делилось.
Получается, что нам необходимо получить последовательность MU, для которой n = 0 (деление 0 на 3 происходит без остатка). Но эту строку получить из MI, с соблюдением указанных правил, мы не можем, поскольку для MI n = 1, а единица на 3 не делится.