Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111)
заменить (111, 2)
заменить (222, 11)
заменить (1, 2)
КОНЕЦ ПОКА
КОНЕЦ
Определите количество таких натуральных N из интервала [234 567 900; 789 012 345], для которых в результате применения данной программы к строке, состоящей из N единиц, получится строка, состоящая только из трех символов.
Проанализируем работу Редактора, для этого приведём код на языке Python.
for N in range (1,100):
s = '1' * N
while ('111' in s):
s=s.replace('111','2',1)
s=s.replace('222','11',1)
s=s.replace('1','2',1)
if len(s) == 3:
print(s,N)
Получаем закономерность, числа идут через промежутки 2, 3 и 11. Получаем группы по 3 числа, которые меняются с периодичностью 16 (2+3+11). Посчитаем количество подходящих чисел.
Приведём код на языке Python.
с = 0
for i in range(234_567_900//16, 789_012_345//16+1):
if 234_567_900 <= 16*i+8 <= 789_012_345:
с += 1
if 234_567_900 <= 16*i+10 <= 789_012_345:
с += 1
if 234_567_900 <= 16*i+13 <= 789_012_345:
с += 1
print(с)
Ответ: 103958333.