Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Дана программа для редактора:
НАЧАЛО
ПОКА НЕ нашлось (00)
заменить (01, 1023)
заменить (02, 310)
заменить (03, 102)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними были только цифры 1, 2 и 3. После выполнения данной программы получилась строка, содержащая 96 единиц, 0 двоек и 75 троек. Выведите минимальную длину исходной строки.
Количество символов до работы Редактора:
X01 + X02 + X03 + 2 = S0,
Когда, редактор начнёт свою работу: X1 + X3 + 2 = S — количество символов после работы Редактора.
По условию задачи X2 = 0.
Рассмотрим цепочки действий Редактора и как они влияют на конечное кол-во (единиц и троек). Понятно, что двойки в этом алгоритме убывают.
Цепочки для единиц:
1) 01–1023–13103–131102–1311310 (количество единиц после попадания на 01 — 4, после полного формата строки 4 · X01),
2) 02–310 (количество единиц после попадания на 02 — 1, после полного формата строки X02),
3) 03–102–1310 (количество единиц после попадания на 03 — 2, после полного формата строки 2 · X03).
Запишем связующее уравнение X1, с начальным количеством (единиц, двоек, троек):
4 · X01 + X02 + 2 · X03 = X1,
где X1 = 96 по условию задачи.
Цепочки для троек:
1) 01–1023–13103–131102–1311310 (количество троек после попадания на 01 — 2, после полного формата строки 2 · X01),
2) 02–310 (количество троек после попадания на 02 — 1, после полного формата строки X02),
3) 03–102–1310 (количество троек после попадания на 03 — 1, после полного формата строки X03).
Запишем связующее уравнение X3, с начальным количеством (единиц, двоек, троек):
2 · X01 + X02 + X03 = X3,
где X3 = 75 — по условию задачи.
Найдем минимальную длину исходной строки с помощью программного кода на языке 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:= (4*X01 + X02 + 2*X03 == 96 and 2*X01 + X02 + X03 == 75)):
S0 = min(S0, X01 + X02 + X03 + 2) # +2, т.к учитываем два нуля в строке
print(S0)
Ответ: 67.

