РЕШУ ЕГЭ — информатика

Задания

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго; i и j  — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m  =  120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

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

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000).

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

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

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

140

100

300

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

140 100

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти,  — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m,  — 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Решение. Сумма a_i и a_j делится на 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++.

#include <iostream>

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;

}

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 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

Ключ