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

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

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

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

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

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

НАЧАЛО

ПОКА нашлось $(5)$ ИЛИ нашлось $(77 )$ ИЛИ нашлось $(222 )$

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Найдите сумму цифр строки, полученной в результате применения приведённой выше программы к строке $55 ...5577 ...77 22...22 . ◟--◝◜--◞◟--◝◜--◞ ◟-◝ ◜-◞ 10 30 50$

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

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

Изначально была строка $5(10)7(30)2(30).$ Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 20.

$5(10)7(30)2(50) → 7 (50)2(50)$

Второе по приоритету действие — это замена пары семерок на одну семерку. Это действие перестанет выполняться, когда количество семерок не станет 1.

$7 2 → 7 2 (50) (50) (1) (50)$

Далее, необходимо прогонять получаемые строки по алгоритму до тех пор, пока мы не получим конструкцию из одной семерки и какого-то количества двоек, большего или равного 3. Если мы получим идентичную конструкцию, но с другим количеством цифр, то это значит, что выполнение определенного набора действий будет зациклено до тех пор, пока условие наличия одной пятерки, двух семерок или трех двоек не будет нарушено.

$7(1)2(50) → 7(1)5(1)2(47) → 7(3)2(47) → 7(2)2(47) → 7(1)2(47)$

Итак, из $7(1)2 (50)$ мы получили $7(1)2(47),$ значит выполнять те же действия большое количество раз не нужно, мы можем сразу снижать количество двоек.

За один шаг количество уменьшилось на 3, значит нужно вычесть из 50 ближайшее к этому числу значение, кратное 3, т.е. 45.

$7(1)2(50) → 7(1)2(5)$

Теперь снова вручную прогоним полученную строку.

$7(1)2(5) → 7(1)5(1)2(2) → 7(3)2 (2) → 7(2)2(2) → 7(1)2(2)$

Сумма цифр равна $7 + 2 + 2 = 11$

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

s = ’5’ * 10 + ’7’ * 30 + ’2’ * 50
while ’5’ in s or ’77’ in s or ’222’ in s:
    if ’5’ in s:
        s = s.replace(’5’, ’77’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’7’, 1)
    elif ’222’ in s:
        s = s.replace(’222’, ’5’, 1)
print(sum(map(int, s)))

Ответ: 11

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