Задание 12. Информатика. ЕГЭ. Статград. 24.10.2024
- Просмотры: 547
- Изменено: 24 ноября 2024
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах \(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\) единиц, получится строка, состоящая только из двоек.
Решение:
Постараемся понять, для каких \(N\) финальная строка стостоит из одних двоек. Для этого напишем программу
Python
for N in range(3, 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(N, s)
Опуская первые две строчки вывода программы, видим, что строка \(22\) получается для чисел \(9б \, 25б \, 41 \ldots\). Строка \(222\) получается для \(N = 10, \, 26, \, 42, \, \ldots\). А строка \(2222\) получится в итоге для чиесл \(16, \, 32, \, 48, \ldots\). Каждая из трех последовательностей \(N\) является арифметической прогрессией с разностью прогессии \(16\). Т.о., задача свелась к подсчёту кодичества чисел, имеющих в остатке от деления на \(16\) числа \(0, \, 9, \, 10\).
Так как \(123456794 = 10 \,\, (\mod 16)\). И \((678901234 - 123456794) // 16 = 34715277\), то количество чисел на указанном в задаче интервале, которые имеют в остатке от деления на \(16\) число \(10\) равно \(34715278\). Аналогичные подсчёты показывает, что количество чисел, имеющих в остатке \(0\) при делении на \(16\) такое же количество, а имеющих остаток \(9\) всего \(34715277\) чисел. Общее количество \(N\), удовлетворяющих условию задачи будет \(34715278 + 34715278 + 34715277\)
Ответ: \(104~145~833\)