Ниже мы рассмотрим решение последней задачи ЕГЭ по информатике, которая была представленная в демонстационной версии КИМ 2020 года.

Данное задяние из разряда высокого уровня (очень высокого уровня), для решения которой авторы КИМ отводят 55 минут.

Максимальный балл за верно выполненное задание - 4.

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

Вот именно это условие мы положим в основу решения данного задания.

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

Затем мы рассмотрим полное решение, удовлетворяющее условиям эффективности, котрое может быть оценено в 4 балла.

Обратите внимание на то, что именно такой ход решения данного задания рекомендуют авторы.

Дело в том, что если вы обладаете достаточными компетенциями в области программирования, то вам не составит труда с самого начала написать код, удовлетворяющий условиям эффективности.

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

Итак, приступим к выполнению задания.

Эффективная и неэффективная программы будут представленны вместе с объяснением ниже, каждое в отдельной вкладке.

Согласно условию, в первой строке данных задается количество чисел последовательности n. В последовательности целых положительных чисел рассматриваются все пары элементов a_i и a_j, такие что i < j и a_i > a_j.

i и j – порядковые номера чисел в последовательности входных данных.

Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120.

Примем обозначения для искомых чисел: Left – первое число, Right – второе число.

{tab Неэффективное решение}

Наиболее простым, но неэффективным, решением будет использование массива.

Последовательность натуральных чисел записывается в массив. Затем производится перебор элементов массива - состаляются пары элементов, которые проверяются на соответствие условию задачи (максимальная сумма элементов делится на m = 120). В случае, если пара элементов соответсвует условию, то значения этих переменных необходимо будет записать в Left и Right, которые необходимо обнулить в самом начале программы.

Перебор элементов цикла будет осуществляться циклами: основной цикл - выбор одного элемента пары, вложенный цикл - выбор второго элемента пары.

Таким образом, мы имеем следующие переменные и констансты:

- i и j – порядковые номера чисел в последовательности входных данных;
- N - количество элементов в последовательности;
- Left – первое число, Right – второе число;
- a - массив размерностью 120000;
- m - констанста, на которую должна делиться пара элементов, равная 120.

 Составим алгоритм решения задачи:

Прогограмма на языке программирования Паскаль:

  const
      m=120;
  var N, i, j, left, right:integer;
      a:array[1..12000] of integer;
begin
  left:=0;
  right:=0;
  read(N);
  for i:=1 to N do
    readln(a[i]);
  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) and 
         ((a[i]+a[j])>(left+right)) then
          begin
            left:=a[i];
            right:=a[j]
          end;
   writeln(left, ' ',right)
end.

{tab Эффективная программа}

Готовится к публикации

{/tabs}