Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли
Дана программа для редактора:
НАЧАЛО
ПОКА НЕ нашлось (00)
заменить (02, 101)
заменить (11, 2)
заменить (12, 21)
заменить (010, 00)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная
Заметим, что сумма цифр исходной строки будет на единицу больше суммы цифр полученной строки.
Приведём решение данной задачи на языке Python.
def is_prime(x):
for i in range(2, (x//2)+1):
if x % i == 0:
return False
return True
for i in range(69, 100):
r = i * 1 + i * 2 - 1
if is_prime(r):
print(i)
break
Ответ: 76.
Приведём решение Бориса Савельева на языке Python.
from random import shuffle
minA = 10**10
for i in range(142, 200, 2):
for j in range(0, 40):
s = list('1' * (i//2) + '2' * (i//2))
shuffle(s)
s = '0' + ''.join(s)+'0'
s1 = s.count('1')
while not '00' in s:
s = s.replace('02', '101', 1)
s = s.replace('11', '2', 1)
s = s.replace('12', '21', 1)
s = s.replace('010', '00', 1)
suma = s.count('1') + s.count('2') * 2
f = 0
for t in range(2, suma):
if suma % t == 0:
f = 1
break
if f == 0:
minA = min(minA, s1)
print(minA)