Slider

Ответ. Задание 27. Досрочный ЕГЭ 2020 года, Информатика

Условие задачи

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

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

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

5

34

12

51

52

51

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

51 51

Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.

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

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

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

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

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

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

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

Ответ

Разность двух чисел четна, если оба числа одинаковой четности. Максимальная сумма элементов получится, если оба элемента будут максимальными.

Программа читает числа и запоминает в переменную max17_0 наибольшее четное, кратное 17, в max0 – наибольшее четное, не совпадающее с max17_0, в max17_1 - наибольшее нечетное, кратное 17, в max1 – наибольшее нечетное, не совпадающее с max17_1.

Сумма двух целых положительных чисел наибольшая, если наибольшее их произведение, поэтому программа сравнивает произведения (max17_0 * max0) и (max17_1 * max1) и множители большего произведения запоминает в переменные a и b.

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

var max17_0, max0, max17_1, max1, i, n, dat, a, b : int;

begin

     max17_0 := 0;  {четный максимум кратный 17}

     max0 :=0; {четный максимум}

     max17_1 :=0; {нечетный максимум кратный 17}

     max1 :=0; {нечетный максимум}

     a:=0;

     b:=0;

     readln(n);                     {ввод количества чисел последовательности}

     for i := 1 to n do

     begin

          readln(dat);      {ввод очередного числа}

          if  (dat mod 2 = 0) then

               if (dat mod 17 = 0) and (dat > max17_0) then  begin

                    if (max17_0 > max0) then

                         max0 :=max17_0;

                    max17_0 := dat

               end

               else

                    if dat > max0 then

                         max0 := dat;

          if  (dat mod 2 <> 0) then

               if (dat mod 17 = 0) and (dat > max17_1) then  begin

                    if (max17_1 > max1) then

                         max1 :=max17_1;

                    max17_1 := dat

               end

               else

                    if dat > max1 then

                         max1 := dat

     end;

     if (max17_0 * max0 = 0) and (max17_1 * max1 = 0) then begin            {не нашлось таких пар}

          a:=0;

          b:=0

     end

     else

          if (max17_0 * max0 > max17_1 * max1) then begin

               a:= max17_0;

               b:=max0

          end

          else begin

               a:= max17_1;

               b:=max1

          end;

     writeln(a, ' ', b)

     end.

 

Назад