Задача к ЕГЭ по информатике на тему «исполнитель «редактор»

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

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

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

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

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось $(45)$ ИЛИ нашлось $(72)$

ЕСЛИ нашлось $(44 )$

ТО заменить $(44,2)$

ИНАЧЕ ЕСЛИ нашлось $(77)$

ТО заменить $(77,2)$

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось $(55 )$

ТО заменить $(55,5)$

ИНАЧЕ ЕСЛИ нашлось $(22)$

ТО заменить $(22,2)$

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Сколько цифр 2 получится в строке, полученной в результате применения приведённой выше программы к строке: $7◟7-.◝.◜.77◞2◟2-.◝.◜.22◞4◟4-.◝.◜.44◞ 5◟5..◝.◜55◞? 40 20 80 40$

Решение руками

Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: $A , (B)$ где A — цифра, которая находится в строке, а B — количество этих цифр.

Изначально была строка $7(40)2(20)4(80)5(40).$ Пока все четверки не заменятся количество двоек в два раза меньшее, чем изначальное количество четверок, они не перестанут исчезать. Вместе с ними исчезают и пятерки, не заменяясь ни на что. Стоит заметить, что на последней итерации вместо исчезновения последней пятерки произойдет исчезновение первой встреченной в строке двойки. В результате мы получим следующую строку:

$7(40)2(19)2(40)5(1)$

Далее действия, которые происходили с четверками, произойдут и с семерками. В результате за следующие 40 итераций получится следующая строка:

$2 7 2 2 5 → 2 7 2 2 5 → 2 7 2 2 5 → 2 7 2 2 5 → 2 7 2 2 5 (1) (38) (18) (40) (1) (2)(36) (18) (40) (1) (1) (36) (18) (40) (1) (2) (34) (18)(40)(1) (1) (34) (18$

Как можно заметить, в какой-то момент начала уменьшать количество семерок, не затрагивая количество двоек. Так будет происходить до момента исчезновения всех семерок. Остановимся на последних итерациях:

$2(1)7(2)2(18)2(40)5(1) → 2(2)2 (18)2(40)5(1) → 2(1)2(18)2(40)5(1)$

На этом программа остановится. Таким образом, количество оставшихся двоек равно 59.

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

s = ’7’ * 40 + ’2’ * 20 + ’4’ * 80 + ’5’ * 40

while ’45’ in s or ’72’ in s:
    if ’44’ in s:
        s = s.replace(’44’, ’2’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’2’, 1)
    if ’55’ in s:
        s = s.replace(’55’, ’5’, 1)
    elif ’22’ in s:
        s = s.replace(’22’, ’2’, 1)

count_of_twos = s.count(’2’)
print(count_of_twos)

Ответ: 59

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