ЕГЭ 2023 по информатике: Разбор 12 задания (Python)

Задание №12 ЕГЭ по информатике относится к повышенному уровню сложности, на его выполнение отводится около 6 минут. Заданием является выполнение алгоритмов для исполнителя, часто включающих циклы и ветвления. Подавляющее большинство (95% и более) заданий использует исполнителя «Редактор».

Исполнитель «Редактор»

Исполнитель «Редактор» принимает на вход строку (обычно состоящую из цифр) и преобразует её согласно заданному алгоритму. Он способен выполнять две команды: заменить и нашлось. Для решения задач с этим исполнителем необходимо переписать алгоритм на языке программирования Python.

Примеры решения задач

Рассмотрим примеры решения задач с исполнителем «Редактор».

Задача 1: Простая замена

Условие: Исполнитель «Редактор» получает на вход строку цифр и преобразует её. Есть команда заменить. Необходимо узнать, какая строка получится после применения программы к строке из 101 единицы.

Программа:

Пока нашлось 3 единицы, заменить три единицы на две двойки.
Пока нашлось 3 двойки, заменить три двойки на две единицы.

Решение:

Создаем исходную строку S из 101 единицы: S = ‘1’ * 101
Реализуем алгоритм на Python:

S = '1' * 101
S = S.replace('111', '22', 1)
S = S.replace('222', '11', 1)
print(S)

Третий аргумент replace (1) указывает на количество замен за одну итерацию. Результат: 112

Задача 2: Вложенные условные конструкции

Условие: Дана программа для исполнителя «Редактор», работающая со строкой, где первая и последняя цифры – четверка, а между ними – 125 шестерок.

Программа:

Пока нашлось 63, заменить 63 на 4.
Иначе, если нашлось 664, заменить 664 на 5.
Иначе, если нашлось 6665, заменить 6665 на 3.

Решение:

Создаем исходную строку: S = ‘4’ + ‘6’ * 125 + ‘4’
Реализуем алгоритм на Python:

S = '4' + '6' * 125 + '4'
if '63' in S:
    S = S.replace('63', '4', 1)
elif '664' in S:
    S = S.replace('664', '5', 1)
elif '6665' in S:
    S = S.replace('6665', '3', 1)
print(S)

Результат: 43

Задача 3: Перебор вариантов и множества

Условие: Программа для исполнителя «Редактор». Начальная строка состоит не менее чем из двух цифр 8 и не содержит других цифр. Сколько различных строк может получиться?

Программа:

Пока нашлось три пятерки, заменить их на одну восьмерку.
Пока нашлось три восьмерки, заменить их на две пятерки.

Решение:

Используем цикл for для перебора количества восьмерок в исходной строке (начиная с двух).
Используем множество для хранения уникальных результатов.

raz = set()
for i in range(2, 1001): # Пример диапазона, может потребоваться корректировка
    S = '8' * i
    while '555' in S:
        S = S.replace('555', '8', 1)
    while '888' in S:
        S = S.replace('888', '55', 1)
    raz.add(S)
print(len(raz))

Результат: 7

Задача 4: Сумма цифр результирующей строки

Условие: Программа для исполнителя «Редактор», применяемая к строке из 200 пятерок. Найти сумму цифр результирующей строки.

Программа:

Пока нашлось три пятерки, заменить их на одну тройку.
Пока нашлось три тройки, заменить их на одну пятерку.

Решение:

Создаем исходную строку: S = ‘5’ * 200
Реализуем алгоритм и вычисляем сумму цифр:

S = '5' * 200
while '555' in S:
    S = S.replace('555', '3', 1)
while '333' in S:
    S = S.replace('333', '5', 1)
summa = sum(int(i) for i in S)
print(summa)

Результат: 16

Задача 5: Обработка строки со специальным символом

Условие: Программа для исполнителя «Редактор», применяемая к строке, начинающейся с символа «>», затем 20 единиц, 15 двоек и 40 троек (в произвольном порядке). Определить сумму числовых значений цифр результирующей строки.

Программа:

Пока нашлось «>1», заменить на «22>».
Пока нашлось «>2», заменить на «1>2».
Пока нашлось «>3», заменить на «1>22».

Решение:

Создаем исходную строку (порядок цифр не важен): S = ‘>’ + ‘1’ * 20 + ‘2’ * 15 + ‘3’ * 40
Реализуем алгоритм и вычисляем сумму:

S = '>' + '1' * 20 + '2' * 15 + '3' * 40
while '>1' in S:
    S = S.replace('>1', '22>', 1)
while '>2' in S:
    S = S.replace('>2', '1>2', 1)
while '>3' in S:
    S = S.replace('>3', '1>22', 1)
summa = sum(int(i) for i in S if i.isdigit())
print(summa)

Результат: 140

Задача 6: Минимальная длина входной строки

Условие: Исходная строка состоит более чем из 300 пятерок. После работы алгоритма – одна пятерка и одна восьмерка. Указать минимальную длину входной строки.

Программа: (Та же, что в задаче 4)

Решение:

for i in range(301, 1000): # Пример диапазона
    S = '5' * i
    while '555' in S:
        S = S.replace('555', '8', 1)
    while '888' in S:
        S = S.replace('888', '55', 1)
    if S.count('5') == 1 and S.count('8') == 1:
        print(i)
        break

Результат: 305

Задача 7: Максимальное количество единиц

Условие: Исходная строка содержит более 184 единиц. Определить минимальную длину исходной строки, при которой результирующая строка содержит максимальное количество единиц.

Программа:

Пока нашлось четыре единицы, заменить их на одну двойку.
Пока нашлось две двойки, заменить их на две единицы.

Решение:

max_count = 0
min_len = 0
for i in range(185, 1000): # Пример диапазона
    S = '1' * i
    while '1111' in S:
        S = S.replace('1111', '2', 1)
    while '22' in S:
        S = S.replace('22', '11', 1)
    if S.count('1') > max_count:
        max_count = S.count('1')
        min_len = i
print(min_len)

Результат: 187

Задача 8, 9: (Объединены ввиду сходства)

Задачи 8 и 9 требуют значительных вычислительных ресурсов для полного перебора. Для эффективного решения необходимо использовать более сложные алгоритмы, выходящие за рамки примеров базового уровня.

Решение задач 12 задания ЕГЭ по информатике на Python требует внимательности к деталям алгоритма, правильного использования циклов и условных операторов, а также умения работать со строками. Применение множеств и генераторов может значительно упростить решение некоторых задач. Не забывайте о возможности перебора вариантов и поиска крайних значений (минимума или максимума).