Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА НЕ нашлось (00)
заменить (02, 101)
заменить (11, 2)
заменить (012, 30)
заменить (010, 00)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка содержала ровно два нуля – на первом и на последнем месте, 50 двоек, больше 100 единиц и не содержала других цифр. После выполнения программы получилась строка, сумма цифр которой оказалась простым числом. Какое наименьшее количество единиц могло быть в исходной строке?
Решение 1
Распишем все переходы для пар из единиц и двоек.
Задача у нас про сумму цифр, как видим сумма при переходе пар константна.
Рассмотрим переходы одиночных цифр между нулями.
Как видим, сумма оба раза уменьшилась на единицу. Получается, что если изначальная сумма была 
, то сумма после работы алгоритма будет 
, однако если не допустить этих оперпций, то сумма не изменится и так потребуется меньшее количество единиц. Это можно сделать поставив после нуля 25 двоек, затем все единицы, и снова 25 двоек. Начальная сумма цифр 
. Нам необходимо количество единиц 
— это 
, получаем 
— количество единиц.
Решение 2
def is_prime(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return n > 1
for n in range(101, 1000):
s = "0" + ’2’ * 25 + ’1’ * n + ’2’ * 25 + ’0’
while not (’00’ in s):
s = s.replace(’02’, ’101’, 1)
.replace(’11’, ’2’, 1)
.replace(’012’, ’30’, 1)
.replace(’010’, ’00’, 1)
if is_prime(sum(int(x) for x in s)):
print(n)
break