Шешімі: Пара с максимальной суммой
На вход программы поступает последовательность из $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$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Шешім по шагам
5 қадамБудем обрабатывать числа слева направо. Для каждого остатка $r$ по модулю $107$ будем хранить максимальное ранее встреченное число с этим остатком и его значение. Для фиксированного текущего числа $x$ сумма предыдущего числа и $x$ делится на $107$, если остаток предыдущего числа равен $(-x) \bmod 107$.
$$a_i + x \equiv 0 \pmod{107}$$Из-за условия $a_i > a_j$ нужно рассматривать только сохранённые значения, которые больше текущего $x$. Если такой кандидат найден, сумма является допустимой. Среди всех допустимых пар выбираем пару с максимальной суммой.
После обработки текущего числа оно становится кандидатом для последующих элементов. Для каждого остатка достаточно хранить максимальное число: при одинаковом остатке большее число всегда даёт не меньшую сумму с будущим положительным числом и чаще удовлетворяет условию строгого неравенства.
Количество состояний равно $m$, поэтому время работы составляет $O(nm)$, а дополнительная память — $O(m)$. При $m=107$ массивы остатков занимают менее 4 Кбайт при использовании целочисленных массивов подходящего типа; в программе ниже используются обычные списки Python, поэтому для строгого ограничения 4 Кбайт целесообразно выбрать компилируемый язык, например C++.
Пример программы на C++17:
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int m = 107;
const int INF = numeric_limits<int>::min();
vector<int> best(m, INF);
vector<int> bestValue(m, 0);
int answerSum = INF;
int answerFirst = 0;
int answerSecond = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
int need = (m - x % m) % m;
if (best[need] != INF && best[need] > x) {
int currentSum = best[need] + x;
if (currentSum > answerSum) {
answerSum = currentSum;
answerFirst = best[need];
answerSecond = x;
}
}
int r = x % m;
if (best[r] == INF || x > best[r]) {
best[r] = x;
bestValue[r] = x;
}
}
cout << answerFirst << ' ' << answerSecond << '\n';
return 0;
}
Идея: хранить максимальное ранее встреченное число для каждого остатка по модулю $107$ и для каждого текущего числа проверять нужный дополнительный остаток. Сложность — $O(nm)$ по времени и $O(m)$ по памяти; программа приведена на C++17.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только делимость суммы, но забывают условие $a_i > a_j$.
Хранят первое встретившееся число для остатка вместо максимального.
Обновляют данные до проверки текущего числа и тем самым разрешают использовать элемент в паре с самим собой.
Используют массив, зависящий от $n$, нарушая требование постоянной памяти.
Перебирают все пары и получают сложность $O(n^2)$.