Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли
Дана программа для Редактора:
НАЧАЛО
ПОКА НЕ нашлось (00)
ЕСЛИ нашлось (011)
ТО
заменить (011, 101)
ИНАЧЕ
заменить (01, 40)
заменить (02, 20)
заменить (0222, 1401)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная
Какое наименьшее количество четвёрок может быть
Приведем решение на языке Python.
d = set() # сохраним сюда все результаты
def move(k1, k2, kk1, kk2, c, last):
# k1, k2 - сколько осталось ед. и дв., kk1, kk2 - текущие замены Х
if len(d) and c > min(d): return # если c > минимума, решение не подходит
if kk1 == 8 and kk2 == 13 and c > 1 and kk1 + kk2 + c == k1+k2 +c: # если условия совпали, а количество цифр в строке такое же
d.add(c) # добавляем текущее количество четверок
if last == 0: # если предыдущая команда не {0222, 1401}, можно выполнить любую
if k1 > 0: move(k1-1, k2, kk1-1, kk2, c+1, 0) # выполняем, если можно
if k2 >= 4: move(k1+2, k2-3, kk1+2, kk2-3, c+1, 1) # выполняем, если можно
elif last == 1: # иначе можно выполнить только команду {01, 40}
if k1 > 0: # выполняем, если можно
move(k1-1, k2, kk1-1, kk2, c+1, 0)
# перебираем варианты количества единиц и двоек
for k in range(100):
move(k, k, k, k, 0, 0)
print(min(d))
Ответ: 5.
Приведем решение Бориса Савельева на языке Python.
a=[]
from random import shuffle
for i in range (1,50):
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)
s = s.replace('0222', '1401', 1)
if s.count('1')==8 and s.count('2')==13:
a.append(s.count('4'))
print(min(a))