Карточки
Тесты
Главная
Курсы
Подписка
12. Выполнение алгоритмов для исполнителей: #298423
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке $\underbrace{100\ldots00}_{55}$, т.е. к строке, состоящей из единицы, за которой следуют $55$ нулей подряд. В ответе запишите только количество нулей в получившейся строке.
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 001)
ИНАЧЕ заменить (1, 00)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦЕдиница в строке всё время ровно одна: замена $10 \to 001$ её сохраняет, замена $1 \to 00$ уничтожает, а появиться новой неоткуда. Поэтому достаточно следить за тем, сколько нулей стоит справа от единицы.
Основная ветка. Пока справа от единицы есть хотя бы один нуль, цепочка $10$ находится, и работает замена $10 \to 001$. Что она делает: убирает один нуль справа от единицы и дописывает два нуля слева от неё. Единица как бы сдвигается вправо через строку, оставляя за собой по два нуля вместо одного.
Баланс нулей за такой шаг: $-1$ справа и $+2$ слева, то есть общее количество нулей растёт на $1$.
Сколько таких шагов. Справа от единицы изначально $55$ нулей, и каждый шаг съедает ровно один, поэтому замена $10 \to 001$ сработает $55$ раз. К этому моменту нулей станет $55 + 55 = 110$, а единица окажется последним символом строки.
Завершающий шаг. Теперь цепочки $10$ нет, но единица есть, поэтому срабатывает ветка ИНАЧЕ: $1 \to 00$, что добавляет ещё $2$ нуля. Единиц в строке не остаётся, условие цикла становится ложным, и программа завершается. Всего цикл отработал $56$ шагов.
Итого нулей: $110 + 2 = 112$ (и это вся длина строки, поскольку единицы в ней больше нет).
Общая формула для $k$ нулей на входе: $2k + 2$. Проверка на малых значениях: при $k = 1$ получается $4$, при $k = 2$ — $6$, при $k = 3$ — $8$; при $k = 55$ имеем $2 \cdot 55 + 2 = 112$.
def run(s):
while '1' in s:
if '10' in s:
s = s.replace('10', '001', 1) # только первое вхождение
else:
s = s.replace('1', '00', 1)
return s
print(run('1' + '0' * 55).count('0')) # 112
20
