Информатика ЕГЭ 27 задание разбор

27-е задание: «Обработка строк или последовательности чисел; сложность алгоритмов»
Уровень сложности — высокий,
Максимальный балл — 4,
Примерное время выполнения — 55 минут.

Набор данных, состоящих из пар чисел

Разбор 27 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

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

  
Задание Б (более сложное, чем А)
Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

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

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

Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Например:
2  6
4  1
7  3
2  9
7  4
sum=231

Показать решение:

✎ Задание Б (алгоритм), более сложное, 4 балла:

  • поскольку в задании указано, что «имеется набор данных, состоящих из пар…», то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:
  • n:longint; {количество пар чисел};
  • объявим сами числа типа integer, переменную цикла — i — типа integer и дополнительные переменные, смысл которых будет объяснен ниже. Объявление сделаем в отдельных строках (так делать не обязательно), чтобы можно было ввести удобно комментарии:
  •  x,y: integer; {пара чисел}
     max: integer; {максимальное из пары}
     min: integer; {минимальное из пары}
     sum:longint; {сумма квадратов отобранных чисел}
     min_kvadr:longint; {мин. нечетная разница квадратов max и min}
     i:integer;
  • так как в задании не оговаривается, что пары чисел считывается из файла, значит их необходимо считать со стандартного входного потока оператором readln(); т.е. организуем цикл:
  • for i:=1 to n do begin
      readln(x,y);
      ...

    Допустим имеем пары:

    2 6
    4 1
    7 3
    2 9
    7 4
    
  • Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:
  • 2 6
    4 1
    7 3
    2 9
    7 4
    
  • но сначала определим максимальное и минимальное число из каждой пары:
  • if x>y then 
    begin 
       max:=x; min:=y 
    end
    else 
    begin 
        max:=y;min:=x 
    end;
  • далее суммируем квадраты максимальных чисел:
  • sum:=sum+sqr(max);
  • поскольку, согласно заданию, сумма должна быть нечетной, то в случае, если сумма будет четной, нам необходимо выбрать пару, в которой разница между квадратами чисел минимальна и при этом нечетна и взять из этой пары не максимальный, а минимальный элемент. Или лучше просто вычислить разницу между квадратами максимума и минимума и затем вычесть ее из получившейся четной суммы. Выделим пару, разница между квадратами чисел которой минимальна и при этом нечетна:
  • 2 6 - разница 32 (36 - 4)
    4 1 - разница 15 (16 - 1)
    7 3 - разница 40 (49 - 9)
    2 9 - разница 77 (81 - 4)
    7 4 - разница 33 (49 - 16)
    
  • поиск минимальной и нечетной разницы между квадратами чисел в паре:
  • if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
        min_kvadr:=sqr(max) - sqr(min)
  • для переменной, обозначающей разницу, до цикла необходимо назначить максимально возможное значение:
  • min_kvadr:=1073676289;  {32 767 * 32 767 (самое большое в типе integer) }
  • таким образом, в цикле у нас происходит:
  • 1. поиск максимального и минимального числа из пары;
  • 2. вычисляется сумма максимальных чисел из каждой пары;
  • 3. находится минимальная разница квадратов максимального и минимального числа в парах.
  • после цикла необходимо проверить сумму на нечетность. Если сумма четная (чего НЕ должно быть по условию), то отнимем от суммы вычисленную минимальную разницу. Но при этом учтем, что если не нашлось нечетной минимальной разницы, то выводим 0 (по условию):
  • if sum mod 2 = 0 then begin
      if min_kvadr = 1073676289 then sum := 0
      else sum:=sum - min_kvadr
    end;

Эффективная программа на языке Паскаль (версия Pascal ABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var
 n:longint; {количество пар чисел}
 x,y: integer; {пара чисел}
 max: integer; {максимальное из пары}
 min: integer; {минимальное из пары}
 sum:longint; {сумма квадратов отобранных чисел}
 min_kvadr:longint; {мин. нечетная разница квадратов max и min}
 i:integer;
begin
sum:=0;
readln(n);
min_kvadr:=1073676289;  {32 767 * 32 767, самое большое integer}
for i:=1 to n do begin
  readln(x,y);
  if x>y then begin max:=x; min:=y end
  else begin max:=y;min:=x end;
  sum:=sum+sqr(max);
  if((max-min) mod 2 > 0) and (sqr(max)-sqr(min) < min_kvadr) then
    min_kvadr:=sqr(max) - sqr(min)
end;
if sum mod 2 = 0 then begin
  if min_kvadr = 1073676289 then sum := 0
  else sum:=sum - min_kvadr
end;
writeln('sum=',sum)
end.

Пример работы программы:

3
1 4
2 4
3 4
sum=41

✎ Задание А (более легкое, 2 балла максимум):

  • так как в задании указано, что пар чисел ровно 5, то введем в программу константу n=5
  • Решение на языке Паскаль (версия PascalABC):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    
    const n = 5; {количество пар чисел}
    var
    x,y: longint; {пара чисел}
    max_sum: longint; {максимальная из сумм}
    sum:array [1..15]of longint; {суммы квадратов всех комбинаций чисел}
    i,k:longint;
    begin
    readln(x,y);
    sum[1]:=sqr(x);
    sum[2]:=sqr(y);
    k:=3; {счетчик для сумм}
    for i:=2 to n do begin
      readln(x,y);
      sum[k]:=sum[k-2]+sqr(x);   {1 шаг: s3=s1+x*x}{2 шаг: s7=s4+x*x}
      sum[k+1]:=sum[k-2]+sqr(y); {1 шаг: s4=s1+y*y}{2 шаг: s8=s4+y*y}
      sum[k+2]:=sum[k-1]+sqr(x); {1 шаг: s5=s2+x*x}{2 шаг: s9=s6+x*x}
      sum[k+3]:=sum[k-1]+sqr(y); {1 шаг: s6=s2+y*y}{2 шаг: s10=s6+y*y}
      k:=k+4;
    end;
    max_sum:=sum[1];
    for i:=1 to n*n do
      if (sum[i]>max_sum) and (sum[i] mod 2 <>0) then max_sum:=sum[i];
    if (max_sum=sum[1]) and (max_sum mod 2 = 0) then max_sum:=0;
    writeln(max_sum)
    end.

📹 Видео


Набор данных, состоящих из троек чисел

Разбор 27 задания ЕГЭ по информатике 2018 года вариант 2 (Крылов С.С., Чуркина Т.Е. «Типовые тренировочные варианты», 10 вариантов):

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

  
А. Имеется набор данных, состоящий из 5 троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу — 2 балла.

Б. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Постарайтесь сделать программу эффективной по времени и по используемой памяти.

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

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

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

Как в варианте А, так и в варианте Б программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Напоминаем! не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

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

Входные данные
Для варианта А на вход программе подается 5 строк, каждая из которых содержит три натуральных числа, не превышающих 10000.
 
Пример входных данных для варианта А:

1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

Для варианта Б на вход программе в первой строке подается количество троек чисел N (1<=N<=100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.   Пример входных данных для варианта Б:

5
1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

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

Примеры аналогичных заданий для тренировки

Показать решение:

✎ Задание Б (4 балла)

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

Пример правильной и эффективной программы для задания Б на языке Паскаль (версия PascalABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const
  aMax = 10000;{наибольшее возможное исходное число}
 
var
  N: longint; {количество троек}
  a, b, c, tmp: longint;{тройка чисел}
  s: longint;{сумма выбранных чисел}
  D_min: longint;{мин. разница в тройке не кратная 5}
  i: longint;{}
 
begin
  s := 0;
  D_min := aMax + 1;
  readln(N);
  for i := 1 to N do 
  begin
    readln(a, b, c);
    if (a > b) then begin tmp := a;a := b;b := tmp end;
    if(b > c) then begin
      tmp := b;b := c;c := tmp;
      if (a > b) then begin tmp := a;a := b;b := tmp end
    end; {a,b,c отсортированы по возрастанию}
    s := s + a;
    if((b - a) mod 5 > 0 ) and ((b - a) < D_min) then D_min := b - a;
    if((c - a) mod 5 > 0 ) and ((c - a) < D_min) then D_min := c - a
  end;
  if s mod 5 = 0 then begin
    if D_min > aMax then s := 0
    else s := s + D_min
  end;
  writeln(s)
end.

✎ Задание А (2 балла)

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

На языке Паскаль (версия PascalABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var
  a: array[1..5, 1..3] of longint; 
  i1, i2, i3, i4, i5: longint; 
  s, sMin: longint;
 
begin
  for i1 := 1 to 5 do 
    readln(a[i1, 1], a[i1, 2], a[i1, 3]); 
  sMin := 100000; 
  for i1 := 1 to 3 do 
    for i2 := 1 to 3 do 
      for i3 := 1 to 3 do
        for i4 := 1 to 3 do
          for i5 := 1 to 3 do 
          begin
            s := a[1, i1] + a[2, i2] + a[3, i3] + a[4, i4] + a[5, i5];
            if (s mod 5 = 0) and (s < sMin) then 
              sMin := s
          end;
  if (sMin = 100000) then 
    sMin := 0; 
  writeln(sMin)
end.

На вход программы поступает последовательность чисел, произвести анализ пар

27_4: Разбор 27 задания ЕГЭ по информатике 2019 года вариант 5 (сборник Крылов С.С., Чуркина Т.Е. «Типовые экзаменационные варианты», 20 вариантов):

Компьютер наземной станции слежения получает от объектов-самолётов, находящихся в зоне её работы, идентификационные сигналы, представляющие собой последовательность из N целых положительных чисел. Каждый объект направляет на наземную станцию уникальное число, т. е. все числа в получаемой станцией последовательности различны. Обработка сигнала представляет собой рассмотрение всех пар различных элементов последовательности, при этом элементы пары не обязаны быть переданы непосредственно друг за другом, порядок элементов в паре не важен. Считается, что возникла одна критическая ситуация, если произведение элементов некоторой пары кратно 58.

Необходимо определить общее количество возникших критических ситуаций.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 < N < 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число: общее количество возникших критических ситуаций.

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

4
2
6
29
87

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

4
Из четырёх заданных чисел можно составить б попарных произведений:

2-6 = 12 
2-29 = 58 
2-87 = 174 
6-29 = 174 
6-87 = 522 
29-87 = 2523

Из них на 58 делятся 4 произведения (выделены синим).

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

Показать решение:

✎ Программа эффективна по времени и по памяти (4 балла):

  • Язык Паскаль (версия PascalABC):
  • var
      N: integer; {количество чисел} 
      a: integer; {очередное число} 
      n58, n29, n2: integer;
      k58: integer; {количество требуемых пар} 
      i: integer;
     
    begin
      readln(N);
      n58 := 0; 
      n29 := 0; 
      n2 := 0; 
      for i := 1 to N do 
      begin
        readln(a);
        if a mod 58 = 0 then 
          n58 := n58 + 1 
        else if a mod 29 = 0 then 
          n29 := n29 + 1 
        else if a mod 2 = 0 then 
          n2 := n2 + 1;
      end;
      k58 := n58 * (n58 - 1) div 2 + n58 * (N - n58) + n2 * n29; 
      writeln(k58)
    end.
  • Произведение двух чисел делится на 58, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
  • A. Оба сомножителя делятся на 58.
  • Б. Один из сомножителей делится на 58, а другой не делится.
  • B. Ни один из сомножителей не делится на 58, но один сомножитель делится на 2, а другой — на 29.
  • Почему именно 2 и 29?
  • Берем два делителя числа 58, произведение которых дает число 58: 2*29 = 58. При этом одно из них — наименьший делитель (в нашем случае 2), а другой, не должен делиться на первый найденный делитель (29/2 <> 0).
  • Условие делимости произведения на 58 можно сформулировать проще, например так:
  • (один из сомножителей делится на 58) 
                        ИЛИ 
    (один сомножитель делится на 2, а другой — на 29)
    
  • Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.
  • При вводе чисел можно определять, делится ли каждое из них на 58, 2 и 29, и подсчитывать следующие значения:
    1. n58 — количество чисел, кратных 58;
    2. n29 —количество чисел, кратных 29, но не кратных 2 и 58;
    3. n2 — количество чисел, кратных 2, но не кратных 29 и 58.
  • Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков.
  • Количество пар, удовлетворяющих условию А, можно вычислить по формуле n58*(n58 - 1)/2.
  • Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n58*(N - n58).
  • Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 * n29.
  • Поэтому искомое количество пар вычисляется по формуле:
  • n58 * (n58 - 1)/2 + n58 * (N - n58) + n2 * n29

✎ Программа неэффективная (2 балла):

  • Язык Паскаль (версия PascalABC):
  • var
      i, j, k, n: integer;
      a: array[1..1000]of integer;//очередное значение
     
    begin
      readln(n);
      for i := 1 to n do 
      begin
        readln(a[i]); 
      end;
      k := 0;
      for i := 1 to n - 1 do 
        for j := i + 1 to n do
          if a[i] * a[j] mod 58 = 0 then 
            k := k + 1;
      writeln(k);
    end.
    Полный перебор: все числа сохраняются в массиве, рассматриваются все возможные пары и подсчитывается количество подходящих произведений.

27_6: Разбор 27 задания демоверсии 2018 года (ФИПИ):

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
  
Пример входных данных:

4
2
6
13
39

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

4
Из четырёх заданных чисел можно составить 6 попарных произведений:

2·6 = 12 
2·13 = 26 
2·39 = 78 
6·13 = 78
6·39 = 234 
13·39 = 507

Из них на 26 делятся 4 произведения:

2·13=26; 
2·39=78; 
6·13=78; 
6·39=234

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

Показать решение:

    Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
    А. Оба сомножителя делятся на 26.
    Б. Один из сомножителей делится на 26, а другой не делится.
    В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой – на 13.

    Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например, так:
    (один из сомножителей делится на 26) ИЛИ
    (один сомножитель делится на 2, а другой – на 13).
    Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.

    При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:
    1) n26 – количество чисел, кратных 26;
    2) n13 – количество чисел, кратных 13, но не кратных 26;
    3) n2 – количество чисел, кратных 2, но не кратных 26.

    Примечание для проверяющего. Сами числа при этом можно не хранить.
    Каждое число учитывается не более чем в одном из счётчиков.
    Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26·(n26 – 1)/2.
    Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26·(N – n26).
    Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2·n13.
    Поэтому искомое количество пар вычисляется по формуле

    n26·(n26 – 1)/2 + n26·(N – n26) + n2·n13

    ✎ Программа на языке Паскаль (версия PascalABC). Программа эффективна и по времени, и по памяти (4 балла):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    
    var
      N: integer; {количество чисел}
      a: integer; {очередное число}
      n26, n13, n2: integer;
      k26: integer; {количество требуемых пар}
      i: integer;
    begin
      readln(N);
      n26 := 0;n13 := 0;n2 := 0;
      for i := 1 to N do 
      begin
        readln(a);
        if a mod 26 = 0 then
          n26 := n26 + 1
        else if a mod 13 = 0 then
          n13 := n13 + 1
        else if a mod 2 = 0 then
          n2 := n2 + 1;
      end;
      k26 := n26 * (n26 - 1) div 2 + n26 * (N - n26) + n2 * n13;
      writeln(k26)
    end.

Разбор 27 задания демоверсии 2019 года (ФИПИ):

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности,
находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Описание входных и выходных данных:
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

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

7
58
2
3
5
4
1
29

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

5
Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений:

 
58·4 = 232     :29=8
58·1 = 58      :29=2
58·29 = 1682   :29=58
2·1 = 2
2·29 = 58      :29=2
3·29 = 87      :29=3

Из них на 29 делятся 5 произведений.

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

Показать решение:

✎ Программа на языке Паскаль (версия PascalABC). Программа неэффективна ни по времени, ни по памяти (2 балла):

  • Перебор всех вариантов произведений:
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    const
      s = 4;//требуемое расстояние
     
    var
      n, i, j, cnt: integer;
      a: array[1..1000] of integer;
     
    begin
      readln(n);
      cnt := 0;
      for i := 1 to n do
        readln(a[i]);
      for i := 1 to n - s do
        for j := i + s to n do
          if a[i] * a[j] mod 29 = 0 then
            cnt := cnt + 1;
      writeln(cnt)
    end.

✎ Программа на языке Паскаль (версия PascalABC). Программа эффективна и по времени, и по памяти (4 балла):

  • Если один из сомножителей делится без остатка на 29, то произведение с любым другим сомножителем тоже будет делится на 29.
  • Последние рассматриваемые 4 элемента можно хранить как 4 счётчика: количество делящихся на 29 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних, всех считанных чисел без 3 последних, – и также сдвигать их после очередного шага.
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    
    const
      s = 4;//требуемое расстояние
     
    var
      n,i: integer;
      n1, n2, n3, n4: integer; //хранение последних s счетчиков
      a_: integer; //очередное значение
      cnt: integer;//количество искомых пар
     
    begin
      readln(n);
      n1 := 0;n2 := 0;n3 := 0;n4 := 0;
      cnt := 0;
      for i := 1 to n do 
      begin
        readln(a_); // очередное значение
        if i > s then
          if a_ mod 29 = 0 then
            cnt := cnt + (i - s)
          else
            cnt := cnt + n4;
        // сдвигаем элементы счетчика
        n4 := n3;
        n3 := n2;
        n2 := n1;
        // обновляем счетчик кратных 29
        if a_ mod 29 = 0 then
          n1 := n1 + 1;
      end;
      writeln(cnt)
    end.

📹 Видео


27_5: Разбор 27 задания ЕГЭ по информатике 2019 года вариант 18 (сборник Крылов С.С., Чуркина Т.Е. «Типовые экзаменационные варианты», 20 вариантов):

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000, — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 8 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

Вам предлагаются два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А — 2 балла.


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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

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

10
5 4
3 2 1
6
7
8 9
4

Программа должна вывести одно число — описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:

16

Показать решение:

    ✎ Задание А (решение на языке Паскаль, версия pascalABC):
    Ниже приводится пример переборного решения на Паскале, неэффективного ни по памяти, ни по времени, но являющегося правильным ответом на задание А.

    const
      s = 8;{требуемое расстояние между показаниями} 
     
    var
      N: integer;
      a: array[1..10000] of integer; {все показания датчика} 
      mp: integer; {минимальное значение произведения} 
      i, j: integer;
     
    begin
      readln(N);
      {Ввод значений датчика} 
      for i := 1 to N do 
        readln(a[i]); 
      mp := 1000 * 1000 + 1;
      for i := 1 to N - s do 
      begin
        for j := i + s to N do 
        begin
          if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp) then 
            mp := a[i] * a[j]
        end;
      end;
      if mp = 1000 * 1000 + 1 then 
        mp := -1; 
      writeln(mp)
    end.

✎Задание Б (решение на языке Паскаль, версия pascalABC):

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

Для каждого показания с номером k, начиная с k = 9, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 8. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.

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

const
  s = 8; {требуемое расстояние между показаниями}
  amax = 1001;{больше максимально возможного показания}
 
var
  N: integer;
  a: array[1..s] of integer; {хранение s показаний датчика} 
  a_: integer; {ввод очередного показания} 
  ma: integer; {минимальное число без s последних} 
  me: integer; {минимальное чётное число без s последних} 
  mp: integer; {минимальное значение произведения} 
  p: integer;
  i, j: integer;
 
begin
  readln(N);
  {Ввод первых s чисел}
  for i := 1 to s do readln(a[i]);
  {Ввод остальных значений, поиск минимального произведения} 
  ma := amax;me := amax;mp := amax * amax;
  for i := s + 1 to N do 
  begin
    readln(a_);
    if a[1] < ma then ma := a[1];
    if (a[1] mod 2 = 0) and (a[1] < me) then me
    := a[1];
    if a_ mod 2 = 0 then p := a_ * ma
    else if me < amax then p := a_ * me
    else p := amax * amax;
    if (p < mp) then mp := p;
    {сдвигаем элементы вспомогательного массива влево}
    for j := 1 to s - 1 do
      a[j] := a[j + 1];
    a[s] := a_
  end;
  if mp = amax * amax then mp := -1;
  writeln(mp)
end.

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить