Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 12. Информатика. ЕГЭ. Статград. 24.10.2024
- Просмотры: 5657
- Изменено: 1 февраля 2025
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах \(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\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования