Систематизация решений задач по информатике (27 ЕГЭ)

Конспект по 27 задачам из ЕГЭ по информатике

 

В последние несколько лет выпускникам в условиях 27 задач предлагают обработать числовые последовательности. Для их успешного решения на 4 балла надо знать следующие правила:

Все задачи на обработку числовых последовательностей можно разбить на два вида:

              I.     рассмотреть все числа последовательности, удовлетворяющие определённым условиям

           II.     рассматривать числа, удовлетворяющие определённым условиям и при этом, отстоящие друг от друга на определённый интервал.

Задачи на 2 балла решаются обычным перебором и, как правило, не вызывают затруднений. На экзамене настоятельно рекомендуется записать решение на 2 балла, а потом – на 4. Баллы выставляются в пользу ученика. В таком случае, есть большая вероятность получения 2 баллов за 27 задачу, если оптимальное решение окажется неправильным. Рассмотрим  конкретные задачи. Сначала на 2 балла (по одной на каждый случай)

Решение на 2 балла

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

 

const MAXN=1000;

var N,i,j,count:integer; a:array[1..MAXN] of integer;

begin

    readln(N);

    for i:=1 to N do

        readln(a[i]);

    count:=0;

    for i:=1 to N-1 do   

           for j:=i+1 to N do 

               if a[i]*a[j] mod 62 = 0 then count:=count+1;

    writeln(count);

end. 

 

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

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

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

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

8

1

3

5

4

6

7

9

8

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

1

 

const d=6; {требуемое расстояние между элементами}

var N: integer; {количество чисел}

      a: array [1..1000] of integer; {исходные данные}

      s: integer; {количество подходящих пар}

      i,j: integer; {счётчики}

begin

   readln(N);

   for i:=1 to N do readln(a[i]);

   s :=0;

   for i := 1 to N-d do begin

     for j := i+d to N do begin

        if (a[i] + a[j]) mod 3 = 0

        then s := s +1;

     end

   end;

   writeln(s);

end.

 

Ещё несколько шаблонов на 2 балла

ЗАДАЧА НА НАИБОЛЬШУЮ СУММУ МЕЖДУ ЭЛЕМЕНТАМИ С РАССТОЯНИЕМ НЕ МЕНЕЕ 5	ЗАДАЧА НА ПОИСК КОЛИЧЕСТВА ПАР, ПРОИЗВЕДЕНИЕ МЕЖДУ ЭЛЕМЕНТАМИ КОТОРЫХ КРАТНО 6
ЗАДАЧА НА ПОИСК КОЛИЧЕСТВА ПАР МЕЖДУ ЭЛЕМЕНТАМИ ПРОИЗВЕДЕНИЕ КОТОРЫХ КРАТНО 14 И РАССТОЯНИЕ МЕЖДУ ЭЛЕМЕНТАМИ НЕ МЕНЕЕ 6	ЗАДАЧА НА ПОИСК ЭЛЕМЕНТОВ, СУММА КОТОРЫХ МАКСИМАЛЬНА, КРАТНА 60, ПРИ ЭТОМ i<j, a[i]>a[j] И РАССТОЯНИЕ МЕЖДУ ЭЛЕМЕНТАМИ НЕ МЕНЕЕ 6

 

Решение на 4 балла

I) Без интервала

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

var N,i,count,x,k62,k2,k31:integer;

begin

    readln(N);

    k2:=0; k31:=0; k62:=0;

    for i:=1 to N do begin

        readln(x);

        if x mod 62 =0 then k62:=k62+1

        else if x mod 2 =0 then k2:=k2+1

        else if x mod 31 =0 then k31:=k31+1

   end;

   count:=k62*(N-k62)+k2*k31+k62*(k62-1)div2;   

   writeln(count);

end. 

 

2) (Сумма кратная 80) Дана последовательность N (2≤N≤10000) целых положительных чисел. Рассматриваются все пары элементов последовательности (числа не превышают 10000), сумма которых делится на m=80. Среди всех таких пар нужно найти и вывести пару с максимальным произведением элементов. Если одинаковое максимальное произведение имеют несколько пар, можно вывести любую из них. Если таких пар нет, нужно вывести два нуля.

Пример
8
10
30
50
40
60
70
90
80    Программа должна вывести 70 90. Из данных 8 чисел можно составить 3 пары, удовлетворяющие условию: (10, 70), (30,50), (70,90). Наибольшее произведение будет в паре (70,90).

const m=80;
var a:array[0..m-1]of integer; N,x,x1,x2,p,pp,max,i:integer;
begin
  for i:=0 to m-1 do a[i]:=0;
  x1:=0; x2:=0; max:=0;
  readln(N);
  for i:=1 to N do begin

    readln(x);

    p:=x mod m; pp:=(m-p) mod m;

    if x*a[pp]>max then

    begin

       max:=x*a[pp];

       x1:=a[pp];

       x2:=x;

    end;

    if x>a[p] then a[p]:=x;

  end;

  writeln(x1,' ',x2);

end. 

 

3) (Разность кратная 80) Дана последовательность N целых неповторяющихся положительных чисел. Рассматриваются все пары элементов последовательности, разность которых делится на m = 80. Среди всех таких пар нужно найти и вывести пару с максимальной разностью элементов. Если одинаковую максимальную разность имеют несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

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

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

8

95

163

5

40

15

3

85

80

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

3 163

Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию: (15, 95), (3, 163), (5, 85). Наибольшая разность получается в паре (3, 163).

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

Будем хранить в одном массиве из m элементов максимальные числа, имеющие соответствующий остаток от деления на m, а в другом – минимальные, и из всех пар максимумов и минимумов выберем пару с наибольшей разностью.

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

 

const m=80;

var  mn,mx:array[0..m-1]of integer;

     x:integer; //очередное число из последовательности

     p:integer; //остаток

     pm:integer; //остаток, дающий лучшую разность

     i,N:integer;

begin    

     for i:=0 to m-1 do

     begin

         mn[i]:= 0; mx[i]:= 0;

     end;

     pm := 0;

     readln(N);

    

     for i:=1 to N do

     begin

         readln(x);

         p:=x mod m;

         if (mn[p] = 0) or (x < mn[p]) then mn[p]:= x;

         if (x > mx[p]) then mx[p]:= x;

         if mx[p]-mn[p] > mx[pm]-mn[pm] then pm := p;

     end;

     if mx[pm] = mn[pm] then writeln('0 0')

     else writeln(mn[pm], ' ', mx[pm]);

end.

 

4) (Максимальная сумма кратная 120) На вход программы поступает последовательность из N (1 ≤ N ≤ 12 000) положительных целых чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом). Найти пару элементов с максимальной суммой, кратной 120. Порядок элементов в паре соответствует порядку в последовательности и первый элемент в паре должен быть больше второго. Гарантируется, что такая пара есть.  

 

const sk=120; var m:array[0..sk-1] of integer;     n,i,a,k,dk,x,y:integer; begin     x:=0; y:=0;     for i:=1 to sk-1 do m[i]:=-11111;     readln(n); readln(a);     k:=a mod sk;     for i:=2 to n do begin       if (m[k]<a) then m[k]:=a;       readln(a);       k:=a mod sk;       dk:=(sk-k) mod sk;       if (m[dk]>a) and (m[dk]+a>x+y) then       begin        x:=m[dk];        y:=a;       end;     end;     writeln(x,' ',y); end.

Пример входных данных   3 240 1200 120 Выходные данные   1200 120

II) С интервалом

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

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

7
26
2
3
5
4
1
13                   Программа должна вывести 5

var i,j,n,k13,k,x,s:integer; a:array[1..4] of integer;
begin
     readln(n);
     for i:=1 to 4 do readln (a[i]);
     k13:=0; k:=0; s:=0;
     for i:=5 to n do begin
          if a[1] mod 13=0 then k13:=k13+1
          else k:=k+1;
          readln(x);
          if x mod 13=0 then s:=s+k+k13
          else s:=s+k13;
          for j:=1 to 3 do a[j]:=a[j+1];
          a[4]:=x;
      end;
      writeln(s);
 end.

В заключении ещё две задачи на числовые последовательности, но не на те правила, что перечислены выше

I Назовём длиной числа количество цифр в его десятичной записи. Например, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых положительных чисел, каждое из которых меньше 10⁸. Необходимо определить, числа какой длины чаще всего встречаются в данном наборе и сколько в нём чисел этой длины. Если числа разной длины встречаются одинаково часто (и чаще чем числа любой другой длины), нужно выбрать большую длину.

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

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

5

15

417

125

32

4801

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

3 2

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

Решение.

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

Var N: integer; {количество чисел}

       a: longint; {очередное число}

       d: array[1..8] of integer; {подсчет}

       mx: integer; {максимальное количество}

       imx: integer; {самая частая длина}

       i,k: integer;

begin

    for i:=1 to 8 do d[i]:=0;

    readln(N);

    for i:=1 to N do begin

        readln(a);

        k:=0;

        while a>0 do begin

            k := k+1;

            a := a div 10;

        end;

        d[k] := d[k]+1;

     end;

     mx := 0;

     for i:=1 to 8 do begin

        if d[i] >= mx then begin

            mx := d[i];

            imx := i;

       end;

     end;

    writeln(imx, ' ', mx)

end.

 

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

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

 

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

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

5

4

15

24

18

31

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

4

У чисел заданного набора чаще всего — по 2 раза — встречаются суммы 4 и 6, в ответе выводится меньшая из них.

Решение.

Наименьшая возможная сумма цифр числа в заданном диапазоне равна 0, наибольшая — 27. Необходимо создать массив с индексами от 0 до 27 и использовать его для подсчёта встречающихся сумм. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение максимального элемента этого массива и вывести его индекс.

 

var     

  N: integer;     {количество чисел}    

  a: integer;     {очередное число}   

  s: integer;     {сумма цифр числа}     

  k: array [0..27] of integer; {подсчёт сумм}    

  imx: integer;   {самая частая сумма}   

  i: integer;

begin    

  for i:=0 to 27 do k[i]:=0;   

  readln(N);   

  for i:=1 to N do begin        

    readln(a);       

    s := 0;        

    while a>0 do begin          

      s := s + a mod 10;            

      a := a div 10;        

    end;        

    k[s] := k[s]+1;    

  end;    

  imx := 0;    

  for i:=1 to 27 do begin        

    if k[i] > k[imx] then imx := i;

  end; 

  write(imx)

  end.