Задание 27 демоверсии ЕГЭ по информатике 2024 года высокого уровня сложности проверяет умение создавать программы для анализа числовых последовательностей. На его выполнение отводится 40 минут, за правильное решение можно получить от 0 до 2 первичных баллов.
Условие задачи
По каналу связи передаётся последовательность целых чисел – показания прибора за N минут. Прибор ежеминутно регистрирует напряжение в условных единицах и передаёт его на сервер. Необходимо определить три переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K минут, а сумма этих трёх чисел была максимально возможной. В ответе нужно записать найденную максимальную сумму. Другими словами, необходимо найти три числа в последовательности, отстоящих друг от друга на расстоянии не менее K минут, с максимальной суммой.
Алгоритм решения
Для решения задачи необходим эффективный алгоритм, поскольку простой перебор всех возможных троек чисел в большом файле будет неэффективен. Предлагаемый алгоритм:
- Чтение данных: Чтение данных из файла A. Файл A содержит значение K (количество минут) и N (количество показаний). Остальные строки файла A содержат числовую последовательность.
- Инициализация переменных: Создаются три переменные: max1, max2 и max3, хранящие три максимальных числа. Для корректной работы алгоритма они инициализируются очень малым числом (например, -10<sup>10</sup>).
- Проход по последовательности: Алгоритм проходит по последовательности чисел, начиная с элемента под индексом K/2.
- Поиск максимумов: На каждом шаге цикла:
- max1 обновляется как максимум из предыдущего значения max1 и элемента, отстоящего от текущего на K/2 элементов.
- max2 обновляется как максимум из предыдущего значения max2 и суммы max1 и элемента, отстоящего от текущего на K элементов.
- max3 обновляется как максимум из предыдущего значения max3 и суммы max2 и текущего элемента.
- Вывод результата: После прохода по всей последовательности, значение max3 содержит максимальную сумму трёх чисел, удовлетворяющих условиям задачи.
Реализация на Python
Пример реализации алгоритма на языке Python (код приведён в сокращённом виде):
f = open("A.txt", "r")
k = int(f.readline())
n = int(f.readline())
data = []
for line in f:
data.append(int(line))
f.close()
max1 = max2 = max3 = -10**10
for i in range(k // 2, n):
max1 = max(max1, data[i - k // 2])
max2 = max(max2, data[i - k] + max1)
max3 = max(max3, data[i] + max2)
print(max3)Рассмотренный алгоритм эффективно находит три числа в числовой последовательности, удовлетворяющие условиям задачи, и вычисляет их максимальную сумму. Данный подход демонстрирует применение алгоритмического мышления и умение работать с файлами и данными, что важно для решения задач на ЕГЭ по информатике. Правильный ответ для файла A в демоверсии – 18960.