На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj (первый элемент пары больше второго; i и j — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).
В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Пример входных данных:
6
60
140
61
100
300
59
Пример выходных данных для приведённого выше примера входных данных:
140 100
Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m = 120: 60 + 300, 140 + 100 и 61 + 59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Сумма ai и aj делится на m, если сумма остатков этих чисел от деления на m равна 0 или m. Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив r длиной m, изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.
Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если r[m–p] > 0, то сумма a и r[m–p] делится на m, и при условии r[m–p] > a эта пара — кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и r[0].
По окончании обработки элемента a необходимо обновить элемент r[p] значением a, если a > r[p]. Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.
const m = 120; {количество различных остатков}var
{хранение максимального значения для каждого из остатков}
r: array[0..m-1] of integer;
n, a, i, p, left, right: integer;
begin
readln(n);
{обнуление массива r}
for i := 0 to m - 1 do
r[i] := 0;
{обнуление переменных для записи ответа}
left := 0; right := 0;
{ввод значений, поиск искомой пары}
for i := 1 to n do
begin
readln(a); {считываем очередное значение}
p := a mod m;
if p = 0 then
begin
if (r[0] > a) and (r[0] + a > left + right) then
begin
left := r[0]; right := a {обновление ответа}
end
end
else
begin
if (r[m - p] > a) and (r[m - p] + a > left + right) then
begin
left := r[m - p]; right := a {обновление ответа}
end
end;
{обновление элемента r для соответствующего остатка}
if a > r[p] then r[p] := a
end;
writeln(left, ' ',right)
end.
Пример 2. Программа на языке Python 3. Программа эффективна по времени и памяти.
m = 120
# создание массива для максимальных значений
# для каждого из остатков
r = [0] * m
# обнуление переменных для записи ответа
left = 0
right = 0
# ввод количества элементов
n = int(input())
# ввод значений, поиск искомой пары
for i in range(n):
a = int(input())
p = a % m;
if r[(m - p) % m] > a and r[(m - p) % m] + a > left + right:
#обновление ответа
left = r[(m - p) % m]
right = a;
# обновление элемента r для соответствующего остатка
if a > r[p]:
r[p] = a
print(left, right)
Пример 3. Программа на языке С++. Программа эффективна по времени и памяти.
#include <iostream>
using namespace std;
int main()
{
int n, a, p, left, right;
int r[120];
int m = 120;
cin >> n;
//обнуление массива r
for (int i = 0; i < m; ++i)
r[i] = 0;
//обнуление переменных для записи ответа
left = 0; right = 0;
// ввод значений, поиск искомой пары
for (int i = 0; i < n; ++i)
{
cin >> a; //считываем очередное значение
p = a % m;
if (p == 0) p = m;
if (r[m - p] > a && r[m - p] + a > left + right)
{
left = r[m - p]; right = a; //обновление ответа
}
// обновление элемента r для соответствующего остатка
if (p < m)
{
if (a > r[p]) r[p] = a;
}
else if (a > r[0]) r[0] = a;
}
cout << left << ' ' << right;
}
Приводим эффективное решение Николая Артюхина на C++.
using namespace std;
int main()
{
int a[120],n, i, x, p, r, m1=0, m2=0;
cin >> n;
for(i=0;i<120;i++){
a[i]=0;
}
for(i=0;i<n;i++){
cin >> x;
p=x%120;
r=(120-p)%120;
if((x+a[r]>m1+m2)&&(a[r]>x)){
m1=a[r];
m2=x;
}
if(x>a[p]) a[p]=x;
}
cout << m1 << " " << m2;
return 0;
}