Ответ: Пара с максимальной суммой
Идея: хранить максимальное ранее встреченное число для каждого остатка по модулю $107$ и для каждого текущего числа проверять нужный дополнительный остаток. Сложность — $O(nm)$ по времени и $O(m)$ по памяти; программа приведена на C++17.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 107$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \le n \le 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности $n$ и параметра $m$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом $n$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Где здесь ошибаются
Проверяют только делимость суммы, но забывают условие $a_i > a_j$.
Хранят первое встретившееся число для остатка вместо максимального.
Обновляют данные до проверки текущего числа и тем самым разрешают использовать элемент в паре с самим собой.
Используют массив, зависящий от $n$, нарушая требование постоянной памяти.
Перебирают все пары и получают сложность $O(n^2)$.