Данное задание проверяет умение создавать программы для анализа числовых последовательностей. Оно считается одним из самых сложных в ЕГЭ по информатике 2022 года. Далее показан способ получения хотя бы одного балла.
Условие задачи
Дана последовательность из n натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, сумма элементов каждой из которых кратна 43. Необходимо найти среди них подпоследовательность с максимальной суммой и определить её длину. Если таких подпоследовательностей несколько, в ответе указывается количество элементов самой короткой из них.
Входные данные задаются в двух файлах: A и B. Каждый файл содержит в первой строке количество чисел n, а в следующих n строках — по одному натуральному числу, не превышающему 10000. Пример входных данных предоставлен, выходные данные отсутствуют. В ответе необходимо указать два числа: длину искомой подпоследовательности для файла A и для файла B.
Решение для файла A (переборный алгоритм)
Файл A содержит 776 чисел. Для него применим переборный алгоритм. Это примитивное решение, но позволяет получить один балл. Необходимо уметь работать со списками (или массивами) и циклами с условием.
Этапы решения:
- Чтение данных: Файл открывается, первая строка (количество чисел n) считывается и преобразуется в целое число. Остальные строки считываются и преобразуются в целочисленный тип данных с использованием генератора списка.
- Инициализация переменных: Создаются переменные:
- максимум: для хранения максимальной суммы (начальное значение 0).
- мин_лен: для хранения минимальной длины подпоследовательности (начальное значение — 1000).
- Перебор подпоследовательностей: Вложенные циклы перебирают все возможные подпоследовательности. Внешний цикл определяет начальный индекс (i), внутренний — конечный индекс (j).
- Вычисление суммы и проверка условия: Для каждой подпоследовательности вычисляется сумма её элементов. Проверяется, кратна ли сумма 43.
- Обновление максимальной суммы и минимальной длины: Если сумма кратна 43 и:
- больше максимум, или
- равна максимум, но длина подпоследовательности меньше мин_лен,
то максимум и мин_лен обновляются.
- Вывод результата: Выводится значение мин_лен.
Решение для файла B (эффективный алгоритм)
Файл B содержит около 5 миллионов чисел. Переборный алгоритм неприменим из-за чрезмерного времени выполнения. Необходимо использовать эффективный алгоритм.
Этапы решения:
- Чтение данных: Числа из файла считываются последовательно.
- Создание списков: Создаются два списка длиной 43:
- мин_сум: для хранения минимальных сумм с остатками от деления на 43 (0…42). Заполняется очень большими числами.
- мин_лен: для хранения минимальных длин подпоследовательностей с остатками от деления на 43 (0…42). Заполняется нулями.
- Итерация и обновление списков: Для каждого числа вычисляется текущая сумма. Остаток от деления суммы на 43 определяет индекс в списках мин_сум и мин_лен. Если текущая сумма минус минимальная сумма с таким же остатком больше текущего максимума или длина меньше текущей минимальной длины, то обновляются значения максимума и минимальной длины.
- Заполнение списков: Если текущая сумма меньше минимальной суммы с соответствующим остатком, то минимальная сумма обновляется. Минимальная длина также обновляется.
- Вывод результата: Выводится минимальная длина (мин_лен) для остатка 0 (сумма кратна 43).
Задание 27 ЕГЭ по информатике требует глубокого понимания алгоритмов и умения выбирать эффективный подход в зависимости от объёма данных. Переборный алгоритм подходит для небольших файлов, для больших файлов необходим более сложный, но эффективный алгоритм, использующий свойства делимости. Понимание этих принципов позволяет успешно решить это задание.