Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в которых v и w обозначают последовательности цифр.
А) заменить (v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (121, 3) преобразует строку 112112 в строку 1312.
Если в строке нет вхождений последовательности v, то выполнение команды не изменяет исходную строку.
Б) Нашлось (v).
Эта команда проверяет, встречается ли последовательность v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для редактора:
НАЧАЛО
ПОКА нашлось (777) или нашлось (99)
ЕСЛИ нашлось (777) ТО заменить (777, 922)
ИНАЧЕ заменить (99, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какое наибольшее количество двоек получится в результате применения приведённой программы к строке, состоящей из 200 цифр 7, 12 цифр 2, 87 цифр 9, идущих в произвольном порядке. В ответе запишите количество двоек в полученной строке.
Решение руками
Нам будут выгодны строки, в которых девятка стоит перед каждой группой из 3 семёрок, затем оставшиеся девятки, затем оставшиеся семерки и в конце двойки. Взглянем на программу, чтобы выяснить, почему так: при замене 3 семерок мы получаем 922, вспоминаем, что перед каждой группой семерок стоит девятка, тогда этот блок будет выглядеть так 9922, каждая пара девяток будет заменена на 1 двойку, тогда в результате получим 222, следовательно каждый элемент 9777 будет заменен на 222.
Решение программой
s = ’9777’ * 66 + ’9’ * 21 + ’7’ * 2 + ’2’ * 12
while ’777’ in s or ’99’ in s:
if ’777’ in s:
s = s.replace(’777’, ’922’, 1)
else:
s = s.replace(’99’, ’2’, 1)
print(s.count(’2’))