Решение: Максимальная сумма пары
На вход программы поступает последовательность из $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$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
7 шаговПеребирать все пары нельзя: такой алгоритм имеет сложность $O(n^2)$. Числа нужно обрабатывать слева направо, чтобы в момент обработки числа $x$ рассматривать только ранее встречавшиеся числа.
$$i < j$$Сумма двух чисел делится на $111$, если сумма их остатков по модулю $111$ равна нулю. Для текущего числа $x$ нужен предыдущий элемент с остатком $r = (111 - x \bmod 111) \bmod 111$.
$$(a_i + x) \bmod 111 = 0$$Для каждого остатка $r$ храним только максимальное ранее встречавшееся число с таким остатком. Если оно больше текущего $x$, то оно образует допустимую пару $a_i > x$, а максимальность сохранённого числа даёт максимальную сумму для данного остатка.
$$best[r] = \max\{a_i : a_i \bmod 111 = r\}$$После нахождения допустимой пары сравниваем её сумму с лучшей найденной суммой и сохраняем значения пары. Затем обновляем массив для остатка текущего числа. Обновление выполняется после проверки, чтобы число не могло образовать пару само с собой.
$$S = a_i + x$$Массив содержит всего $111$ элементов, поэтому память постоянна: $O(111) = O(m)$. Время обработки каждого числа постоянно, следовательно, общая сложность составляет $O(n)$.
Пример программы на Python 3. При отсутствии подходящего предыдущего числа используется значение $-1$, так как все входные числа положительны.
Программа:
$$best = [-1] * 111\nmax_sum = -1\nanswer_a = answer_b = 0\n\nn = int(input())\nfor _ in range(n):\n x = int(input())\n need = (-x) % 111\n a = best[need]\n\n if a > x:\n current_sum = a + x\n if current_sum > max_sum:\n max_sum = current_sum\n answer_a = a\n answer_b = x\n\n rem = x % 111\n if x > best[rem]:\n best[rem] = x\n\nprint(answer_a, answer_b)$$Алгоритм с массивом максимумов по остаткам: время $O(n)$, память $O(111)$; например, программа на Python 3 с обработкой чисел слева направо.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары и получать сложность $O(n^2)$.
Проверять только делимость суммы на $111$, но забывать условие $a_i > a_j$.
Обновлять максимум для текущего числа до проверки пары и тем самым разрешать использовать число само с собой.
Хранить для каждого остатка не максимальное, а последнее встретившееся число: это может привести к потере пары с большей суммой.
Искать остаток как $111 - (x \bmod 111)$ без дополнительного взятия по модулю: для остатка $0$ получится ошибочный остаток $111$.