Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, сумма которых делится на m = 80. Среди всех таких пар нужно найти и вывести пару с максимальным... | Яндекс.Репетитор

Задание#T30180

Дана последовательность целых положительных чисел. Рассматриваются все пары элементов последовательности, сумма которых делится на

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

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

В первой строке входных данных задаётся количество чисел (

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

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

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

Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию:

Наибольшее произведение получается в паре

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

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

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

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

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

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

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

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

Показать разбор

Содержание верного ответа

(допускаются иные формулировки ответа, не искажающие его смысла)

Сумма двух чисел кратна если сумма остатков от деления этих чисел на кратна При этом для получения максимального произведения из чисел с одинаковыми остатками нужно выбирать наибольшее.

Будем хранить в массиве из элементов максимальное число, имеющее соответствующий остаток от деления на

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

Ниже приведена программа на алгоритмическом языке, реализующая этот алгоритм.

Решение 1. Правильная и эффективная программа на алгоритмическом языке

алг задача27 
нач
  цел m = 80
  цел таб a[0:m-1]
  цел N
  цел x | очередное число из последовательности
  цел x1,x2 | ответ - пара чисел
  цел p,pp | остаток и парный ему остаток
  цел i

  нц для i от 0 до m-1
    a[i] := 0
  кц
  x1 := 0;  x2 := 0
  ввод N
  нц N раз
    ввод x
    p := mod(x,m)
    pp := mod(m-p,m)
    если x*a[pp] > x1*x2
      то x1 := a[pp]; x2 := x
    все
    если x > a[p]
      то a[p] := x
    все
  кц
  вывод x1, ' ', x2
кон

В приведённом решении в переменную записывается остаток от деления на очередного числа из последовательности, а в переменную – парный к нему остаток, то есть тот остаток, который должен быть у второго числа пары, чтобы сумма чисел делилась на При вычислении учитывается особый случай, когда заданное число делится на то есть

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

Порядок проверки условий (сначала обновление произведения, затем – элемента массива) важен. Если сначала обновить массив, то при

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

В программе нет специальной проверки наличия в последовательности подходящих пар, но если их нет, переменные и сохранят заданные в начале программы нулевые значения и будет выведен верный ответ.

Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Подобная программа оценивается не выше баллов.

Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).

Решение 2. Правильная, но неэффективная программа на языке Паскаль

const m=80;
var 
    N: integer;     {количество чисел}
    a: array [1..10000] of integer;  {исходные данные}
    x1, x2: integer;     {ответ – пара чисел}
    i,j: integer;

begin
    readln(N);
    for i:=1 to N do readln(a[i]);
    x1:=0; x2:=0;
    for i := 1 to N do begin
        for j := i+1 to N do begin
            if ((a[i] + a[j]) mod m = 0) and
               (a[i]*a[j] > x1*x2)
            then begin
                x1:=a[i]; x[2]:=a[j]
            end
        end
    end;
    writeln(x1, ' ', x2)
end.

Указания по оцениванию

Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бόльшая из двух оценок. Описание алгоритма решения без программы оценивается в баллов.

Критерии оценки

4 баллаПрограмма правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел и параметра время работы пропорционально
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1. пропущен или неверно указан знак пунктуации;
2. неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования;
3. не описана или неверно описана переменная;
4. применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку

3 баллаНе выполнены условия, позволяющие поставить балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел но может зависеть от
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой аналогичной структуре данных).
Количество синтаксических ошибок («описок»), указанных в критериях на балла, – не более пяти.
Допускается наличие не более одной ошибки следующих видов:
1. ошибка при вводе данных (не считывается значение или неверно организован ввод последовательности);
2. ошибка при инициализации или отсутствие инициализации там, где она необходима;
3. используется неверный тип данных;
4. использована одна переменная (константа) вместо другой;
5. используется один знак операции вместо другого;
6. отсутствует вывод ответа или выводится не то значение (например, выводится произведение вместо пары чисел);
7. неверная работа с массивом, в том числе выход за границы массива;
8. пропущены или неверно расставлены операторные скобки (при использовании языков с операторными скобками);
9. неверно обрабатываются элементы, кратные

2 баллаНе выполнены условия, позволяющие поставить или балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на балла, и до девяти синтаксических ошибок, описанных в критериях на балла.
ИЛИ
Программа работает в целом верно и эффективно по времени, но в ней есть не подходящие под перечень из критериев на балла ошибки, которые в некоторых особых случаях приводят к неверным результатам.
ИЛИ
Представлено корректное переборное решение, в котором все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например выход индексов за границы массива, рассмотрение произведений вида

и т. д.

1 баллНе выполнены условия, позволяющие поставить

или балла.
При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками:
1. рассматриваются пары с подходящей суммой;
2. обнаруживается и выводится пара с максимальным произведением

0 балловНе выполнены условия, позволяющие поставить

или балла

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 2 тыс. раз. С ним справились 69% пользователей.

Это задание в разделах:

Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей

Это задание в тестах:

Тренировочный вариант ЕГЭ по информатике №45

Задание#T30180

Это задание в разделах:

Это задание в тестах:

Рекомендованные задания