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