Ответ: Максимальная сумма пары
Вывести описание однопроходного алгоритма и программу на Python 3, хранящую постоянное число кандидатов для каждой чётности.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p = 21$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время $O(N)$ и использовать объём памяти, не зависящий от $N$ и не превышающий 1 Кбайт.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Где здесь ошибаются
Проверять только значения чисел, а не количество их вхождений: пара из двух одинаковых значений допустима только при наличии двух соответствующих элементов.
Рассматривать только пары, в которых оба числа делятся на $21$, хотя по условию достаточно делимости хотя бы одного элемента.
Не разделять числа по чётности.
Сохранять всю последовательность, нарушая ограничение по памяти.
Использовать двойной перебор всех пар, что даёт сложность $O(N^2)$.