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