Пара с максимальной суммой
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на $m = 107$. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел $n$ ($2 \le n \le 12\,000$). В каждой из последующих $n$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности $n$ и параметра $m$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом $n$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Условие как в банке ФИПИ — открыть и сверить
| На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj (первый элемент пары больше второго, i и j порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 107. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть. Пример входных данных: 6 60 114 61 100 261 46 Пример выходных данных для приведённого выше примера входных данных: 114 100 Пояснение. Из шести заданных чисел можно составить 3 пары, сумма элементов которых делится на 107: 60+261, 114+100, 61+46. Во второй Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет боьшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию. | ||
| |
Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.
Открыть разбор1Мягкая — с чего смотретьуровень 1 из 3
Как при последовательном чтении очередного числа учитывать только те предыдущие числа, которые могут образовать подходящую пару?
2Наводящая — какие числа считатьуровень 2 из 3
Для каждого остатка по модулю $m$ храните лучший ранее встреченный кандидат: максимальное число, которое больше текущего числа и имеет нужный остаток.
3Прямая — фактически решениеуровень 3 из 3
Так как все числа не превосходят $10\,000$, можно хранить максимум и само число для каждого возможного остатка. При чтении $x$ перебирайте остатки $r$, для которых $r \equiv -x \pmod m$, и проверяйте условие предыдущего числа $>x$.