Шешімі: Пара с максимальной суммой
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 117$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \le n \le 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать элементы искомой пары. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу. Эффективная по времени программа должна иметь линейную зависимость времени работы от $n$ и $m$. Память, необходимая для хранения переменных программы, не должна увеличиваться с ростом $n$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Шешім по шагам
7 қадамПоследовательность просматривается слева направо. В момент обработки числа $x = a_j$ в таблице уже находятся только элементы $a_i$ с индексами $i < j$, поэтому порядок элементов пары автоматически соблюдается.
$$i < j$$Сумма $y + x$ делится на $117$, если остаток числа $y$ равен $(-x) \bmod 117$. Для каждого остатка храним максимальное предыдущее число с таким остатком и само число для вывода.
$$(y + x) \bmod 117 = 0$$Если найденное число $y$ больше текущего $x$, пара удовлетворяет условию $a_i > a_j$. Её сумма сравнивается с максимальной найденной суммой.
$$y > x$$После проверки текущего числа обновляем максимум для остатка $x \bmod 117$. Это позволяет рассматривать каждый элемент постоянное число раз.
$$O(n + m) = O(n)$$Память алгоритма зависит только от числа остатков, то есть от $m$, и не зависит от $n$. При $m = 117$ используется таблица из $117$ позиций.
$$O(m)$$Программа на Python 3.10:
```python
m = 117
n = int(input())
# best[r] = максимальный найденный элемент с остатком r
best = [None] * m
max_sum = -1
answer_first = answer_second = None
for _ in range(n):
x = int(input())
need = (-x) % m
y = best[need]
if y is not None and y > x:
current_sum = y + x
if current_sum > max_sum:
max_sum = current_sum
answer_first = y
answer_second = x
r = x % m
if best[r] is None or x > best[r]:
best[r] = x
print(answer_first, answer_second)
```
Алгоритм использует максимальный предыдущий элемент для каждого остатка по модулю 117; сложность — $O(n + m)$ по времени и $O(m)$ по памяти.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять все пары и получать квадратичную сложность $O(n^2)$.
Не учитывать порядок элементов и использовать числа, встретившиеся после текущего.
Проверять только делимость суммы, но не проверять условие $a_i > a_j$.
Хранить первый встретившийся элемент остатка вместо максимального.
Забыть обновлять таблицу после обработки текущего элемента.