Жауабы: Пара с максимальной суммой
Алгоритм использует максимальный предыдущий элемент для каждого остатка по модулю 117; сложность — $O(n + m)$ по времени и $O(m)$ по памяти.
У этого задания официального ключа нет, поэтому ответ получен в разборе және кілтпен салыстырылмаған. Нәтижені жаттамас бұрын, өтіңіз выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $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$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Где здесь ошибаются
Проверять все пары и получать квадратичную сложность $O(n^2)$.
Не учитывать порядок элементов и использовать числа, встретившиеся после текущего.
Проверять только делимость суммы, но не проверять условие $a_i > a_j$.
Хранить первый встретившийся элемент остатка вместо максимального.
Забыть обновлять таблицу после обработки текущего элемента.