1. Как решать задание ЕГЭ

1. Тип ответа: запись числовых значений.

 

2. Структура содержания: умение создавать собственные программы (\(20\)–\(40\) строк) для анализа числовых последовательностей.

 

3. Уровень сложности задания: высокий.

 

4. Примерное время выполнения: \(40\) минут.

 

5. Количество баллов: \(2\).

 

6. Требуется специальное программное обеспечение: да.

 

7. Задание: умение анализировать числовые последовательности.

 

Пример задания (демоверсия \(2022\))

 

Дана последовательность из \(N\) натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие, что сумма элементов каждой из них кратна \(k = 43\). Найди среди них подпоследовательность с максимальной суммой, определи её длину.

 

Если таких подпоследовательностей найдено несколько, в ответе укажи количество элементов самой короткой из них.

 

 

Даны два входных файла (27_A.txt и 27_B.txt), каждый из которых содержит в первой строке количество чисел \(N\) (\(1 ≤ N ≤ 10 000 000\)). Каждая из следующих \(N\) строк содержит одно натуральное число, не превышающее \(10 000\).

 

Пример организации исходных данных во входном файле:

 

\(7\)

\(1\)

\(3\)

\(4\)

\(93\)

\(8\)

\(5\)

\(95\)

 

В ответе укажи два числа: сначала значение искомой длины для файла \(A\), затем — для файла \(B\).

 

Предупреждение: для обработки файла \(B\) не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

 

Метод, которым мы воспользуемся — метод префиксных сумм — заключается в том, что сумма \(N\) вычисляется с начала последовательности из \(x\) элементов, параллельно вычисляется сумма \(M\) с начала последовательности из \(y\) элементов последовательности (\(y<x\)) — эти суммы назовём префиксными. Для достижения необходимых свойств суммы искомой подпоследовательности из \(N\) вычитается \(M\).

 

 

После считывания количества элементов организуем два списка: в одном из списков Pref_s будем хранить префиксные суммы под индексом, равным остатку от деления на \(43\), а в другом Pref_l — длины префиксных сумм.

 

При считывании элемента из файла вычисляем сумму всех предшествующих ему элементов (s), остаток от деления на \(43\), проверяем, есть ли префиксная сумма с таким остатком в списке Pref_s; если нет, то записываем, если есть, то проверяем, является ли эта сумма минимальной, а её длина — максимальной, так как по условию нам нужна максимальная сумма минимальной длины. Значит, из текущей суммы нужно вычесть минимальную префиксную сумму максимальной длины.
 

 

 

Ответ: \(27\)_A — \(185\), \(27\)_B — \(844158\).