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

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

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

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

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

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

НАЧАЛО

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

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

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

Изначально была строка $5(60)4(30)2(90)7(120).$

Условно первый блок программы – это исчезновение пятерок с четверками и появление на их месте 30 двоек. Это происходит за счет замены 2 пятерок на одну двойку, т.е. произойдет 30 замен, а также 30 раз 2 четверки заменятся на 1 (29 раз сотрется четверка). Стоит заметить, что последняя четверка не сотрется, вместо нее сотрется первая попавшаяся в строке семерка. В итоге получится следующая строка:

$2(30)4(1)2(90)7(119)$

Далее все двойки, стоящие до четверки, заменятся на 7.

$2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 (30) (1) (90) (119) (1) (28) (1) (90)(118) (2) (26) (1) (90) (118) (1)(26)(1) (90) (118) (2) (24) (1) &#x0$

Можно заметить, что в определенный момент программа доходит до уменьшения количества двоек перед четверкой без добавления новых семерок в начале строки или удаления семерок из группы, находящейся в конце. Это будет происходить до полного удаления группы двоек перед четверкой. В результате получим следующую строку:

$7 4 2 7 (1) (1) (90)(118)$

Похожие действия произойдут с группой двоек после четверки:

$7(1)4(1)2(90)7(118) → 7(1)4(1)7(1)2(88)7(117) → 7(1)4 (1)7(2)2(86)7(117) → 7(1)4(1)7(1)2(86)7 (117)$

Как видно, после достижения отметки 28 в количестве двоек программа начинает их уменьшать, не затрагивая семерки. Таким образом после выполнения программы останется следующая строка:

$7(1)4(1)7(1)7 (117)$

Сумма цифр равна $7 ⋅ 119 + 4 = 837.$

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

s = ’5’ * 60 + ’4’ * 30 + ’2’ * 90 + ’7’ * 120

while ’54’ in s or ’27’ in s:
    if ’55’ in s:
        s = s.replace(’55’, ’2’, 1)
    elif ’22’ in s:
        s = s.replace(’22’, ’7’, 1)
    if ’44’ in s:
        s = s.replace(’44’, ’4’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’7’, 1)

sum_of_digits = sum(int(digit) for digit in s)
print(sum_of_digits)

Ответ: 837

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