12.02 Исполнитель «Редактор» – строка с произвольным порядком цифр

Аналитическое решение

Заметим, что при заменах комбинаций и в результате получается комбинация, оканчивающаяся на и . Тогда можно расписать полную замену, с учётом нескольких команд сразу. Получится следующий результат:

Пусть в исходной строке было единиц, двоек и троек соответственно. Тогда будет выполнено переходов , и . Получится, что в конечном выражении все переходы дают по одной единице, двойки дают переходы (причем один переход даёт две двойки), тройки дают переходы . Тогда получим следующую систему уравнений:

Решив систему из этих трёх уравнений получим одно решение — , то есть количество троек в исходном выражении равно 6.

Решение программой

# Будем перебирать количество единиц, двоек и троек
for c1 in range(100):
    for c2 in range(100):
        for c3 in range(100):
            s = ’0’ + c1 * ’1’ + c2 * ’2’ + c3 * ’3’  # Порядок цифр для алгоритма не важен

            # Осуществляем алгоритм
            while (’01’ in s) or (’02’ in s) or (’03’ in s):
                s = s.replace(’01’, ’2302’, 1)
                s = s.replace(’02’, ’10’, 1)
                s = s.replace(’03’, ’201’, 1)

            # Проверка, что в итоге получается строка, соответствующая условию
            if (s.count(’1’) == 51) and (s.count(’2’) == 29) and (s.count(’3’) == 23):
                print(c3)  # Вывод ответа, после этого нужно остановить программу