Карточки
Тесты
Главная
Курсы
Подписка
12. Выполнение алгоритмов для исполнителей: #298424
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $81$ идущей подряд цифры $1$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (88888, 888)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКонструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у первой ветки: пока в строке есть $1111$, вторая ветка не работает вовсе.
Первая фаза. Строка из $81$ единицы. Каждый шаг превращает $1111$ в $888$: единиц становится на четыре меньше, восьмёрок на три больше, причём восьмёрки копятся слева, а единицы остаются справа. Так как $81 = 4 \cdot 20 + 1$, замена сработает $20$ раз, после чего останется хвост из одной единицы, а слева накопится $3 \cdot 20 = 60$ восьмёрок. Строка принимает вид из $60$ восьмёрок и одной единицы.
Вторая фаза. Четырёх единиц подряд больше нет, включается вторая ветка: $88888 \to 888$, то есть восьмёрок каждый раз становится на две меньше. Замена возможна, пока восьмёрок не меньше пяти. Убавляем по две от чётного числа $60$: $60, 58, 56, \ldots, 6, 4$. На четырёх восьмёрках цепочка $88888$ уже не находится, и цикл завершается. Это $\frac{60 — 4}{2} = 28$ шагов.
Хвост из одной единицы всё это время не трогается: четыре единицы подряд там взяться неоткуда. Итого остаются $4$ восьмёрки и $1$ единица: $88881$. Всего цикл отработал $20 + 28 = 48$ шагов.
Обратите внимание: ответ определяется остатком от деления $81$ на $4$ (длина хвоста из единиц) и чётностью числа восьмёрок. Здесь $60$ чётно, поэтому процесс упирается ровно в $4$ восьмёрки; если бы восьмёрок было нечётное число, осталось бы $3$.
def run(s):
while '1111' in s or '88888' in s:
if '1111' in s:
s = s.replace('1111', '888', 1) # только первое вхождение
else:
s = s.replace('88888', '888', 1)
return s
print(run('1' * 81)) # 88881
Проверка на малых значениях подтверждает логику: строка из $8$ единиц даёт $8888$, из $9$ — $88881$, из $12$ — $888$, из $13$ — $8881$.
20
