Решение: Максимальная сумма пары
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 120$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \le n \le 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности $n$ и параметра $m$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом $n$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговОбрабатываем последовательность слева направо. Поэтому все сохранённые элементы автоматически имеют индекс меньше индекса текущего элемента, что обеспечивает условие $i < j$.
Если текущий элемент равен $x$, то для делимости суммы на $120$ предыдущий элемент $y$ должен иметь остаток $(120 - x \bmod 120) \bmod 120$.
$$y \bmod 120 = (120 - x \bmod 120) \bmod 120$$Для каждого остатка храним только максимальный ранее встреченный элемент. Это достаточно: среди элементов с одним и тем же остатком больший элемент образует с текущим $x$ большую сумму. Если максимальный элемент больше $x$, условие $a_i > a_j$ выполнено.
Для найденной подходящей пары сравниваем сумму с максимальной найденной ранее суммой и сохраняем пару с большей суммой.
После проверки текущего элемента обновляем максимальное значение для его остатка. Используется массив из $120$ элементов, поэтому дополнительная память не зависит от $n$, а время работы составляет $O(n)$.
Язык программирования: Python 3.11.
Программа:
$$m = 120\nmax_by_rem = [-1] * m\nbest_sum = -1\nbest_pair = (0, 0)\n\nn = int(input())\nfor _ in range(n):\n x = int(input())\n need = (m - x % m) % m\n y = max_by_rem[need]\n\n if y > x and y + x > best_sum:\n best_sum = y + x\n best_pair = (y, x)\n\n rem = x % m\n if x > max_by_rem[rem]:\n max_by_rem[rem] = x\n\nprint(best_pair[0], best_pair[1])$$Алгоритм работает за $O(n)$ времени и использует $O(m)$ дополнительной памяти; при $m = 120$ память постоянна и не зависит от $n$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не проверять условие $a_i > a_j$.
Обновлять данные о текущем числе до проверки пары, из-за чего число может быть использовано само с собой.
Хранить минимум вместо максимума для каждого остатка.
Перебирать все пары, получая сложность $O(n^2)$.
Искать только пары с нужными остатками, но не учитывать порядок элементов.