Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли
Дана программа для редактора:
НАЧАЛО
ПОКА нашлось (01) ИЛИ нашлось (02)
заменить (02, 1110)
заменить (01, 220)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная
Приведём решение на языке Python.
def Div(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
mini = 1000000
for x in range(100):
for y in range(100):
s = '0' + '1'* x + '2'* y
if len(s) > 44:
while ('01' in s) or ('02' in s):
s = s.replace('02','1110',1)
s = s.replace('01','220',1)
if Div(s.count('1') + s.count('2') * 2):
mini = min(mini,x + 2*y)
print(mini)
Ответ: 46.
Приведём решение Бориса Савельева на языке Python.
from random import shuffle
minA = 10**10
for i in range(44, 100):
for k in range(0, i + 1):
for j in range(0, 20):
s = list('1' * k + '2' * (i - k))
shuffle(s)
s = '0' + ''.join(s)
s1 = s.count('1') + s.count('2') * 2
while ('01' in s) or ('02' in s):
s = s.replace('02', '1110', 1)
s = s.replace('01', '220', 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)