Задание 27 ЕГЭ по информатике · 0B12A6

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d=120, и по крайней мере одно из чисел пары делится на p=7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Напишите эффективную по времени и памяти программу для решения этой задачи. Опишите алгоритм решения перед текстом программы и укажите использованный язык программирования и его версию. Программа должна использовать не более 1 Кбайт памяти, а её время работы не должно зависеть от параметра d.

1. Числа рассматриваются по одному. Для каждого остатка от деления на 120 храним два максимальных значения: максимальное число, делящееся на 7, и максимальное число, не делящееся на 7. Вместе с каждым значением сохраняем само число.

2. Для очередного числа x перебираем все остатки r, отличные от x mod 120. Пара допустима, если x делится на 7 или сохранённое число делится на 7. Поэтому при x, кратном 7, можно брать максимальное сохранённое число любого типа, а иначе — только максимальное число, кратное 7.

3. Если найденная сумма больше текущей максимальной суммы, запоминаем пару. После проверки помещаем x в соответствующую группу остатка и при необходимости заменяем хранимый максимум.
O(N⋅d)

4. В данной задаче d=120, поэтому перебор 120 остатков является константным относительно N. Используется постоянное количество переменных и массивов фиксированного размера, то есть память не растёт с N и d.
O(N)

5. Один из вариантов программы на Python 3: