Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Дана программа для редактора:
НАЧАЛО
ПОКА НЕ нашлось (00)
заменить (01, 103)
заменить (02, 201)
заменить (03, 2110)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними были только цифры 1, 2 и 3. После выполнения данной программы получилась строка, содержащая 196 единиц, 75 двоек и 0 троек. Выведите минимальную длину исходной строки.
Приведём решение на языке Python.
# Поиск минимального S0, перебором S0 и переменных X01, X02
for S0 in range(6, 3000):
for X01 in range(1, S0 - 4):
for X02 in range(1, S0 - X01 - 3):
if (f:= (X02 + S0 - 2 == 75 and X01 + X02 + 2 * (S0 - 2) == 196)):
break
if f: break
if f: break
print(S0)
Приведём другое решение на языке Python.
# Поиск минимального S0, перебором переменных X01, X02, X03
S0 = 10**6
for X01 in range(1, 200):
for X02 in range(1, 200):
for X03 in range(1, 200):
if (f:= (X01 + 2*X02 + X03 == 75 and 3*X01 + 3*X02 + 2*X03 == 196)):
S0 = min(S0, X01 + X02 + X03 + 2) # +2, т.к учитываем два нуля в строке
print(S0)
Ответ: 68.