Задача к ЕГЭ по информатике на тему «исполнитель «редактор» – строка с произвольным порядком цифр» №2

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

1. заменить (v, w)

2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03)

заменить(01, 2302)

заменить(02, 10)

заменить(03, 201)

КОНЕЦ ПОКА

КОНЕЦ

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки расположенные в произвольном порядке. После выполнения данной программы получилась строка, содержащая 51 единицу, 29 двоек и 23 тройки. Сколько троек было в исходной строке?

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

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

$01 → 2302 → 2310$
$02 → 10$
$03 → 201 → 22302 → 22310$

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

$x + y+ z = 51$
$x + 2z = 29$
$x + z = 23$

Решив систему из этих трёх уравнений получим одно решение — $x,y,z = 17,28,6$ , то есть количество троек в исходном выражении равно 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)  # Вывод ответа, после этого нужно остановить программу

Ответ: 6