Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли
Дана программа для Редактора:
НАЧАЛО
ПОКА НЕ нашлось (00)
ЕСЛИ нашлось (011)
ТО
заменить (011, 101)
ИНАЧЕ
заменить (01, 40)
заменить (02, 20)
заменить (0222, 1401)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная
Приведем решение на языке Python.
from itertools import product as p
def fn(u):
A = '0' + u + '0'
while '00' not in A:
if '011' in A:
A = A.replace('011', '101', 1)
else:
A = A.replace('01', '40', 1).replace('02', '20', 1).replace('0222', '1401',1)
return A.count('4') if A.count('1') == 6 and A.count('2') == 9 else 10**6
a = [B for i in range(2, 19, 2)\
for B in [''.join(r) for r in p('21', repeat=i) if r.count('1') == i/2]]
print(min([fn(A) for A in a]))
Ответ: 3.
Приведем решение Бориса Савельева на языке Python.
from random import shuffle
a = []
for i in range (1,100):
for j in range (0,1000):
s = list('1'*i+'2'*i)
shuffle(s)
s = '0'+''.join(s)+'0'
while not '00' in s:
if '011' in s:
s = s.replace('011','101',1)
else:
s = s.replace('01', '40', 1)
s = s.replace('02', '20', 1)
if s.count('1') == 6 and s.count('2') == 9:
a.append(s.count('4'))
print(min(a))