Карточки
Тесты
Главная
Курсы
Подписка
12. Выполнение алгоритмов для исполнителей: #298429
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
ЕСЛИ нашлось (25)
ТО заменить (25, 5)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355)
ТО заменить (355, 52)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦНа вход приведённой выше программе поступает строка, начинающаяся с цифры «$3$», а затем содержащая $n$ цифр «$5$» ($n > 3$). Определите наименьшее значение $n$, при котором в строке, получившейся в результате выполнения программы, останутся только цифры «$5$».
Три оператора ЕСЛИ здесь независимы, а не вложены, поэтому за один проход тела цикла выполняется до трёх замен строго в записанном порядке: сначала $25 \to 5$, затем $355 \to 52$, затем $555 \to 3$, причём каждая работает уже с результатом предыдущей.
Посмотрим на первый проход. Строка $3\underbrace{55\ldots5}{n}$: цепочки $25$ нет; $355 \to 52$ превращает начало в $52$, и остаётся $52\underbrace{55\ldots5}{n-2}$; затем $555 \to 3$ съедает три пятёрки из хвоста. Дальше двойки, тройки и пятёрки начинают перемешиваться: $355 \to 52$ порождает двойки, $25 \to 5$ их уничтожает, $555 \to 3$ снова создаёт тройки.
Поведение оказывается крайне неустойчивым по $n$, никакой простой формулы нет. Достаточно взглянуть на маленькие значения: $n = 6$ даёт $5235$, $n = 7$ — $552$, $n = 8$ — $3$, $n = 9$ — $35$. Поэтому надёжный путь — перебрать значения $n$ подряд и найти первое, при котором в результате нет ни двоек, ни троек.
def run(s):
while '25' in s or '355' in s or '555' in s:
if '25' in s:
s = s.replace('25', '5', 1) # только первое вхождение
if '355' in s:
s = s.replace('355', '52', 1)
if '555' in s:
s = s.replace('555', '3', 1)
return s
n = 4
while set(run('3' + '5' * n)) != {'5'}:
n += 1
print(n) # 19
Две типичные ошибки: заменять нужно только первое вхождение (третий аргумент $1$ у replace), и три условия должны проверяться последовательно и независимо — если написать их через elif, ответ изменится.
Перебор даёт первое подходящее значение $n = 19$: программа оставляет строку $55$, состоящую из одних пятёрок. Все меньшие $n$ дают результат, где обязательно есть двойка или тройка ($n = 17$ даёт $352$, $n = 18$ — $52$). Следующие подходящие значения — $23$, $63$, $67$, так что важно брать именно наименьшее.
20
