Решение: Максимальная сумма пары
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 114$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \leq n \leq 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности $n$ и параметра $m$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом $n$.
Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Решение по шагам
7 шаговЧитаем последовательность слева направо. В момент обработки числа $x = a_j$ все сохранённые числа являются элементами с индексами меньше $j$, поэтому условие $i < j$ выполняется автоматически.
Если $r = x \bmod m$, то для делимости суммы на $m$ остаток предыдущего числа должен быть равен $(m-r) \bmod m$.
$$a_i \bmod m = (m - (x \bmod m)) \bmod m$$Для каждого остатка достаточно хранить максимальное ранее встреченное число. Если это число больше $x$, то оно даёт наибольшую возможную сумму с текущим числом среди всех ранее встреченных чисел с нужным остатком.
После проверки текущего числа обновляем максимальное число для остатка $x \bmod m$. Обновление выполняется после проверки, чтобы одно и то же число не использовалось дважды и чтобы сохранялось условие $i < j$.
Количество операций равно $O(n + m)$, а дополнительная память — $O(m)$. При $m = 114$ массив остатков содержит всего 114 элементов и не зависит от $n$.
Программа на Python 3. Для отсутствующих значений используется признак `-1`, так как все входные числа положительны.
Код программы:
m = 114
n = int(input())
max_by_rem = [-1] * m
best_sum = -1
best_first = 0
best_second = 0
for _ in range(n):
x = int(input())
r = x % m
need = (m - r) % m
first = max_by_rem[need]
if first > x:
current_sum = first + x
if current_sum > best_sum:
best_sum = current_sum
best_first = first
best_second = x
if x > max_by_rem[r]:
max_by_rem[r] = x
print(best_first, best_second)
Алгоритм работает за $O(n + m)$ времени и использует $O(m)$ дополнительной памяти; для заданного $m = 114$ память не зависит от $n$. Программа на Python 3 хранит максимальное число для каждого остатка, проверяет условие $a_i > a_j$ и выбирает пару с максимальной суммой, кратной 114.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только делимость суммы, но забывают условие $a_i > a_j$.
Обновляют максимум для текущего остатка до проверки пары и тем самым могут использовать текущее число дважды.
Хранят минимум вместо максимума для каждого остатка.
Перебирают все пары и получают сложность $O(n^2)$.
Неверно вычисляют требуемый остаток: нужно использовать $(m-r) \bmod m$.