Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных:

6

60

140

61

100

300

59

Пример выходных данных для приведённого выше примера входных данных:

140 100

Пояснение. Из шести заданных чисел можно составить 3 пары, сумма элементов которых делится на 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.

Комментарии для проверяющего 1. При таком решении хранится только очередной прочитанный элемент и информация о максимальных значениях, имеющих различные остатки от деления на m (на их хранение будет потрачено не более 4 m байт памяти, а на все переменные в целом – менее 4 килобайт). Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксированно, т.е. не зависит от длины последовательности и даже от величины m. Поэтому при увеличении длины последовательности в k раз время работы программы увеличивается не более чем в k раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается 4 баллами. Программа может не рассматривать отдельно случай p = 0, а учесть оба случая с помощью одной формулы: (m - p) mod m. Такой вариант реализации показан в примере 2 программы на языке Python. Может быть реализовано решение с заменой p = 0 на p = m. Такая программа на языке С++ приведена ниже (пример 3). Все подобные программы оцениваются, исходя из максимального балла – 4 (см. критерии). 2. Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив или другие структуры данных. Такое решение эффективно по времени, но неэффективно по памяти. Оно оценивается, исходя из максимального балла – 3 (см. критерии). Кроме того, возможен неэффективный способ определения, какой именно остаток от деления нас интересует, например с помощью цикла, выполняющегося до m раз, или с помощью m условных операторов: if p = 0 and a > r[0] then r[0] = a; if p = 1 and a > r[1] then r[1] = a; и т.д. Такое решение работает в m раз дольше и оценивается, исходя из максимального балла – 3 (см. критерии). 3. Решение, неэффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается, исходя из максимального балла – 2 (см. критерии)

Пример 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; }

 

Указания по оцениванию	Баллы
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов
Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, не допустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку	4
Не выполнены условия, позволяющие поставить 4 балла. Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел, но может существенно зависеть от m (см. комментарий к эффективному решению задачи). Допускается наличие не более одной содержательной ошибки следующих видов: 1) допущена ошибка при вводе данных (например, не считывается значение N, или числа могут быть считаны, только если будут записаны в одной строке через пробел); 2) неверная инициализация или её отсутствие там, где она необходима; 3) используется неверный тип данных, при этом ошибка не является синтаксической; 4) не более одного раза использована одна переменная (или константа) вместо другой, или не более одного раза используется один знак операции вместо другого, или не более одного раза используется одно зарезервированное слово языка программирования вместо другого, при этом ошибка не является синтаксической; 5) служебное слово else относится не к тому if, к какому следует; 6) отсутствует вывод ответа, или выводится значение не тех переменных; 7) выход за границу массива (в частности, при обращении к m -му элементу массива с индексами от 0 до m –1, даже если он существует, но не заполнен нужным значением); 8) не выполнен или неверно выполнен учёт элементов, остаток от деления которых на m равен 0. 3 балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает верно, эффективно по времени при условии исправления не более трёх содержательных ошибок, описанных в критериях на 3 балла и аналогичных им, и не более девяти синтаксических ошибок, указанных в критериях на 4 балла. При этом в программе могут быть опущены с помощью многоточия однотипные действия, связанные с рассмотрением каждого из остатков от деления на m.   Не допускается выставление 2 баллов за программу, если в ней учитываются суммы вида a[i] + a[i] (в том числе в алгоритме без хранения элементов последовательности). 2 балла также ставится за корректное переборное решение, в котором все числа сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. Пример фрагмента соответствующей программы на языке Паскаль: left:= 0; right:= 0; for i:= 1 to N - 1 do  for j:= i + 1 to N do if (a[i] > a[j]) and ((a[i] + a[j]) mod m = 0) then if a[i] + a[j] > left + right then begin    left:= a[i];    right:= a[j] end; В цикле реализации переборного алгоритма не допускаются выход индексов за границы массива, а также любые логические ошибки	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. При этом программа описывает в целом правильный алгоритм (эффективный или нет) и в ней присутствует не менее двух элементов решения из перечисленных ниже, возможно, реализованных с ошибками: учитывается условие a[i] > a[j]; проверяется делимость суммы на m; ищется пара с максимальной суммой. В случае, если в любом решении содержится не более одного из указанных элементов, программа оценивается в 0 баллов	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4