Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111)
заменить (111, 2)
заменить (222, 11)
заменить (1, 2)
КОНЕЦ ПОКА
КОНЕЦ
Определите количество таких натуральных N из интервала [123 456 794; 678 901 234], для которых в результате применения данной программы к строке, состоящей из 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 s.count('1') == 0:
print(s,N)
Получаем закономерность, числа идут через промежутки 1, 6 и 9. Получаем группы по 3 числа, которые меняются с периодичностью 16 (1+6+9). Посчитаем количество подходящих чисел.
Приведём код на языке Python.
с = 0
for i in range(123_456_794//16, 678_901_234//16+1):
if 123_456_794 <= 16*i+9<= 678_901_234:
с += 1
if 123_456_794 <= 16*i+10 <= 678_901_234:
с += 1
if 123_456_794 <= 16*i+16 <= 678_901_234:
с += 1
print(с)
Ответ: 104145833.