Как научиться решать 27 задание егэ информатика - ExamHelp.top

На уроке рассмотрен разбор 27 задания ЕГЭ по информатике: дается подробное объяснение и решение задания 2017 года

Содержание:

Объяснение задания 27 ЕГЭ по информатике
Решение 27 заданий ЕГЭ по информатике
Задания 2021 и более поздние
Задания предыдущих лет на повторение
- На вход программы поступает последовательность чисел, произвести анализ пар
- Выбрать из каждой пары одно число
- Набор данных, состоящих из троек чисел
- Анализ пар, находящихся на расстоянии

27-е задание: «Анализ числовых последовательностей»

Уровень сложности

— высокий,

Требуется использование специализированного программного обеспечения

— да,

Максимальный балл

— 2,

Примерное время выполнения

— 35 минут.

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

Рекомендации по выполнению:

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

Типичные ошибки и рекомендации по их предотвращению:

ФГБНУ «Федеральный институт педагогических измерений»

Работа с записями

Запись в Паскале — это сложный тип данных, который может состоять из нескольких элементов – полей; поля могут иметь различный тип.

Подробно о записях объясняется здесь.

Решение 27 заданий ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Задания 2021 и более поздние

27_1 new:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.

Входные данные:
Даны два входных файла: файл A (27-1a.txt) и файл B (27-1b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

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

✍ Решение:

Язык PascalABC.NET:

Язык Python (Питон):

f = open ('27-1b.txt') # для первого ответа - 27-1a.txt
n=int(f.readline())
data=f.readlines()
summa=0
minim=10001 # для минимальной разницы
for i in range(0, n):
    s = data[i].split()
    a=int(s[0])
    b=int(s[1])
    summa+=min(a,b) # сумма максимумов из пар
    raznitsa = abs(a-b) # разница
    if raznitsa % 3 != 0:
        minim=min(minim,raznitsa)
if summa % 3 != 0:
    print(summa)
else:
    print(summa + minim) # здесь добавляем! т.к. иначе берем наибольший из пары

Ответ: 67303 200157496

Задания предыдущих лет на повторение

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

27_4:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

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

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

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

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

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.

Язык Python (версия Python 3):

n=int(input())
n58,n29,n2=0,0,0
for i in range(n):
    a=int(input())
    if a % 28 == 0:
        n58+=1
    elif a % 29 == 0:
        n29+=1
    elif a % 2 == 0:
        n2+=1
k58=n58 * (n58-1) // 2 + n58 * (n-n58) + n2 * n29
print(k58)

Язык Бейсик:

N58 = 0
N2 = 0
N29 = 0
NX = 0
INPUT N
FOR I = 1 TO N
   INPUT 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
      ELSE NX = NX + 1
      END IF
    END IF
 END IF
NEXT I
K58 = N58*(N58 - 1)2 + N58*(N2 + N29 + NX) + N2*N29
PRINT K58

Произведение двух чисел делится на 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, и подсчитывать следующие значения:

n58 — количество чисел, кратных 58;
n29 —количество чисел, кратных 29, но не кратных 2 и 58;
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 года:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

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

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

Из четырёх заданных чисел можно составить 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

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

✍ Решение:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

А.

Б.

В.

Примечание для проверяющего. Условие делимости произведения на 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

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

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.

Программа на языке Python (версия Python 3):

n=int(input())
n26,n13,n2=0,0,0
for i in range(n):
    a=int(input())
    if a % 26 == 0:
        n56+=1
    elif a % 13 == 0:
        n13+=1
    elif a % 2 == 0:
        n2+=1
k26=n26 * (n26-1) // 2 + n26 * (n-n26) + n2 * n13
print(k26)

Программа на языке Бейсик:

N26 = 0
N2 = 0
N13 = 0
NX = 0
INPUT N
FOR I = 1 TO N
   INPUT 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
      ELSE NX = NX + 1
      END IF
    END IF
 END IF
NEXT I
K26 = N26*(N26 - 1)2 + N26*(N2 + N13 + NX) + N2*N13
PRINT K26

27_7: Разбор досрочного экзамена 2020 г, ФИПИ (2 вариант):

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

любую из них

. Если подходящих пар в последовательности нет,

нужно вывести два нуля

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

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

57 57

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

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

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

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

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

Типовые задания для тренировки

✍ Решение:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

✎ Программа эффективна по времени и памяти

Язык Pascal (PascalABC):
Вариант 1:

const
  p = 19;
 
var
  N: integer; {количество чисел}
  a: integer; {очередное число}
  m0, m1: integer; {чётный и нечётный максимумы}
  mp0, mp1: integer;  {чётный и нечётный максимумы, кратные p}
  x, y: integer; {ответ – пара чисел}
  i: integer;
 
begin
  m0 := 0; m1 := 0;
  mp0 := 0; mp1 := 0;
  x := 0; y := 0;
  readln(N);
  for i := 1 to N do
  begin
    readln(a);   
     // для четных
    if a mod 2 = 0 then  
    begin
      // если кратное
      if (a mod p = 0) and (a >= mp0) then 
        begin
          if mp0 > m0 then
            m0:= mp0;
          mp0:=a
        end     
        else if a > m0 then 
          m0 := a;
     end
     else 
        begin
    // для нечетных
        if (a mod p = 0)and(a>=mp1) then 
          begin 
            if mp1>m1 then 
              m1:=mp1;
            mp1 := a;
          end
          else if a>m1 then
            m1:=a;
         end;  
  end;
 //  writeln('mp0=', mp0, 'm0=', m0);
  if (mp0 > 0) and (m0 > 0) then
  begin
    x := mp0; y := m0; 
  end; 
 // writeln('mp1=', mp1, 'm1=', m1);
  if (mp1 > 0) and (m1 > 0) and (mp1 + m1 > x + y) then
  begin
    x := mp1; 
    y := m1;
  end;
  writeln('=', x, ' ', y)
end.

Язык Pascal (PascalABC):
Вариант 2:

const
  p = 19;
 
var
  n, i, x, k19n, k19chet, n19chet, n19n, m1, m2: integer;
 
begin
  readln(n); {количество чисел}
  readln(x); {первое число}
  // обнуление всех переменных
 
  k19chet := 0; // четный кратный
  n19chet := 0; // четный некратный
  k19n := 0; // нечетный кратный
  n19n := 0; // нечетный некратный
  m1 := 0; m2 := 0; // максимальные
  // цикл до n - 1, т.к. первое число уже считали
  for i := 1 to n - 1 do
  begin
    // проверка, если четный и кратный
    if (x mod p = 0) and (x mod 2 = 0) and (x > k19chet) then
    begin
      k19chet := x;
    end;
    // проверка, если четный и некратный
    if (x mod p <> 0) and (x mod 2 = 0) and (x > n19chet) then
    begin
      n19chet := x;
    end;
    // проверка, если нечетный и кратный
    if (x mod p = 0) and (x mod 2 = 1) and (x > k19n) then
    begin
      k19n := x;
    end;
    // проверка, если нечетный и некратный  
    if (x mod p <> 0) and (x mod 2 = 1) and (x > n19n) then 
    begin
      n19n := x;
    end;
 
    readln(x); // считываем очередное число
    // если x кратно и есть такое некратное n19chet, сумма с которым была бы больше чем m1 + m2
    if (x mod p = 0) and ((x + n19chet) mod 2 = 0) and (x + n19chet > m1 + m2) and (n19chet > 0) then
    begin
      m1 := x; m2 := n19chet;
    end;
    // если x кратно и есть такое некратное n19n, сумма с которым была бы больше чем m1 + m2
    if (x mod p = 0) and ((x + n19n) mod 2 = 0) and (x + n19n > m1 + m2) and (n19n > 0) then
    begin
      m1 := x; m2 := n19n;
    end;
    // если есть такое кратное k19n, сумма с которым была бы четной и больше чем m1 + m2
    if ((x + k19n) mod 2 = 0) and (x + k19n > m1 + m2) and (k19n > 0) then
    begin
      m1 := x; m2 := k19n;
    end;
    // если есть такое кратное k19chet, сумма с которым была бы четной и больше чем m1 + m2
    if ((x + k19chet) mod 2 = 0) and (x + k19chet > m1 + m2) and (k19chet > 0) then
    begin
      m1 := x; m2 := k19chet;
    end;
  end;
  writeln(m1, ' ', m2)
end.

Язык Python (Python 3)

p = 19
m0 = m1 = mp0 = mp1 = 0
N = int(input())
for i in range(N):
	 a = int(input())
	 if a % 2 == 0:
		 if a % p == 0 and a >= mp0:
			 if mp0 > m0: m0 = mp0
			 mp0 = a
		 elif a > m0: m0 = a
	 else:
		 if a % p == 0 and a >= mp1:
			 if mp1 > m1: m1 = mp1
			 mp1 = a
		 elif a > m1: m1 = a
x = y = 0
if mp0 > 0 and m0 > 0:
	x = mp0; y = m0
if mp1 > 0 and m1 > 0 and mp1 + m1 > x + y:
	x = mp1; y = m1
print(x,y)

Ещё один путь решения – записать всю последовательность в массив и анализировать её в несколько проходов. Ниже приводится реализующая такой алгоритм программа на языке C++. В этой программе массив с исходными данными обрабатывается два раза: на первом проходе находятся индексы максимального чётного и нечётного элементов, кратных p, на втором проходе – общие чётный и нечётный максимумы. При этом элементы, выделенные как кратные при первом проходе, во время второго прохода из сравнения исключаются. Такая программа эффективна по времени (несмотря на повторную обработку массива, общее время работы пропорционально N), но неэффективна по памяти. Максимальная оценка за такую программу при отсутствии в ней синтаксических и содержательных ошибок – 3 балла.

✎ Правильная программа на языке C++, эффективная только по времени

С++:

#include <iostream>
using namespace std;
int main() {
 const int p = 19; // делитель
 int N; cin >> N; // количество элементов
 int a[N]; // элементы последовательности
 for (int i = 0; i < N; ++i) cin >> a[i];
 int imp0 = -1, imp1 = -1; //индексы максимумов, кратных p
 for (int i = 0; i < N; ++i) {
	if (a[i] % p == 0) {
		 if (a[i] % 2 == 0) {
			if (imp0 == -1 || a[i] > a[imp0]) imp0 = i;
		}
		else {
			if (imp1 == -1 || a[i] > a[imp1]) imp1 = i;
		}
	}
 }
 int im0 = -1, im1 = -1; // индексы общих максимумов
 for (int i = 0; i < N; ++i) {
	 if (i != imp0 && i != imp1) {
		 if (a[i] % 2 == 0) {
			if (im0 == -1 || a[i] > a[im0]) im0 = i;
		 }
		 else {
			if (im1 == -1 || a[i] > a[im1]) im1 = i;
		 }
	 }
 }
 int x = 0, y = 0; // пара чисел для ответа
 if (imp0 != -1 && im0 != -1) {
	x = a[imp0]; y = a[im0];
 }
 if (imp1 != -1 && im1 != -1 && a[imp1] + a[im1] > x + y) {
	x = a[imp1]; y = a[im1];
 }
 cout << x << ' ' << y << endl;
 return 0;
}

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

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

Язык Pascal (версия PascalABC):

const
  p = 19;
var
  N: integer; {количество чисел}
  a: array [1..10000] of integer; {исходные данные}
  x, y: integer; {ответ – пара чисел}
  i, j: integer;
begin
  readln(N);
  for i := 1 to N do readln(a[i]);
  x := 0; y := 0;
  for i := 1 to N - 1 do
  begin
    for j := i + 1 to N do
    begin
      if ((a[i] - a[j]) mod 2 = 0) and
            ((a[i] mod p = 0) or (a[j] mod p = 0)) and
      (a[i] + a[j] > x + y)
      then
      begin
        x := a[i]; y := a[j]
      end
    end
  end;
  writeln(x, ' ', y)
end.

Выбрать из каждой пары одно число

27_1:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 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);
  ...

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

Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:

но сначала определим максимальное и минимальное число из каждой пары:

if x>y then 
begin 
   max:=x; min:=y 
end
else 
begin 
    max:=y;min:=x 
end;

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

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):

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.

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

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

так как в задании указано, что пар чисел ровно 5, то введем в программу константу n=5

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

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 задания на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

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

27_2:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

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

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

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

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

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

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

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

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

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

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

Пример входных данных для варианта А:

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

Пример входных данных для варианта Б:

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

Типовые задания для тренировки

✍ Решение:

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

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

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

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):

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_3: Разбор 27 задания демоверсии 2019 года (ФИПИ):

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

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

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

Из 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 произведений.

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

✍ Решение:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

Перебор всех вариантов произведений:

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 последних, – и также сдвигать их после очередного шага.

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.

Смотрите видео разбора демоверсии 2019 года задание 27:
📹 YouTube здесь

Видео на RuTube здесь

27_5:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

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

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

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

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

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

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

✍ Решение:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

✎ Задание А (решение на языке Паскаль, версия 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.

Источник

Привет! Продолжаем набирать форму к ЕГЭ по информатике 2023.

Сегодня рассмотрим некоторые тренировочные задачи из 27 задания ЕГЭ по информатике.

Изучим приём, как решать некоторые типы задач из 27 задания.

Задача (Изучим приём)

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел оканчивалась на 6 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:

Пример входного файла:
6
4 7
3 11
1 9
5 4
7 9
5 1

Для указанных входных данных значением искомой суммы должно быть число 26.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Решение:

Напишем программу на языке Python.

f=open('27_4a.txt')

n=int(f.readline())

sm = [0]*10

for i in range(n):
    a = f.readline().split()
    x, y = int(a[0]), int(a[1])

    sm2=[10**9]*10

    for j in range(10):

        r1=sm[j]+x
        r2=sm[j]+y

        sm2[r1%10] = min(r1, sm2[r1%10])
        sm2[r2%10] = min(r2, sm2[r2%10])

    sm=sm2

print(sm[6])

Чтобы проверить на что оканчивается положительное число, можно воспользоваться остатком от деления на 10.

Список sm — это минимальные суммы, для каждого остатка от деления на 10. Первая ячейка sm[0] — отвечает за минимальную сумму, которая может получится с остатком от деления на 10 равным нулю, вторая ячейка sm[1] — отвечает за минимальную сумму, которая может получится с остатком от деления на 10 равным единице и т.д.

Переменные x и y — числа очередной пары.

Для каждой пары заводим список sm2. Это минимальные суммы, которые могут получится с учётом конкретной пары для каждого остатка. Эти значения опираются на предыдущие значения sm. Приём похож на задание 18 из ЕГЭ по информатике. Там мы тоже опирались на два минимальных значения. Они уже минимальны, нет смысла перебирать все варианты, начиная с самого начала.

r1 — это прибавляем число x к сумме каждого остатка. r2 — это прибавляем число y к сумме каждого остатка.

Но числа r1 и r2 могут попасть не в ту же ячейку, которая была использована при получении этих чисел. Числа r1 и r2 могут обладать другими остатками при делении на 10.

В ячейку для конкретного остатка r1%10 мы выбираем минимальное значение из того, что там было, и нового претендента r1. Ведь r1 может «не победить» старое значение. Старые значения могли получится, когда мы это число x прибавляли к другим ячейкам списка sm. Нам нужно среди всех таких вариантов выбрать самое минимальное значение для ячейки конкретного остатка.

С переменной r2 делаем те же действия. Если у r2 будет такой же остаток (r2%10), как и r1, то всё равно в ячейку запишется самое маленькое значение.

В начале кладём в ячейки списка sm2 очень большое число (10**9), т.к. ищём минимальные значения.

Большие числа (10**9) могут перезаписаться в sm, если для какого-то остатка не удалось собрать сумму. Роли они не сыграют, т.к. проиграют всем по минимальности.

Таким образом, и число x, и число y пробуют провзаимодействовать с каждой из 10 ячеек списка sm. Два числа одновременно не смогут попасть в одну ячейку, и попадёт в эту ячейку самое маленькое значение.

Здесь используется именно новый список sm2 для каждой пары. Мы не можем и отталкиваться от списка sm и сразу обновлять этот список.

После окончания «ЦИКЛА с дестью остатками», список sm2 и будет содержать актуальную информацию для каждого остатка. В sm присваиваем sm2.

Шаг за шагом анализируем каждую пару. Раскладывать её «по спектру» на все 10 остатков. Списки sm и sm2 напоминают 17 задание из ЕГЭ по информатике, когда анализировали пары чисел.

Чтобы получить ответ, достаточно посмотреть в списке sm ячейку с индексом 6.

Ответ:

Задача (Закрепление)

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 9 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Пример входного файла:

6
6 1 9
4 8 11
9 4 6
2 8 3
10 3 5
1 4 5

Для указанных входных данных значением искомой суммы должно быть число 81.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение:

Напишем программу.

f=open('27_5a.txt')

n=int(f.readline())

sm = [0]*9

for i in range(n):
    a = f.readline().split()
    x, y, z = int(a[0]), int(a[1]), int(a[2])

    sm2=[0]*9

    for j in range(9):

        r1=sm[j]+x+y
        r2=sm[j]+x+z
        r3=sm[j]+y+z
        
        if i==0 or sm[j]!=0:
            sm2[r1%9] = max(r1, sm2[r1%9])
            sm2[r2%9] = max(r2, sm2[r2%9])
            sm2[r3%9] = max(r3, sm2[r3%9])

    sm=sm2

print(sm[0])

Решение похоже на программу из предыдущей задачи. В прошлой раз нас интересовали остатки от деления на 10. Здесь нужно собирать максимальные суммы с разными остатками от деления на 9. В нулевой ячейке списка sm будет сидеть максимальная сумма, которая делится на 9.

Теперь мы заставляем провзаимодействовать два числа из каждой тройки с предыдущими суммами. Перебираем все варианты. Вместо функции min(), уже пишем max().

В начале кладём в ячейки списка sm2 нули, т.к. ищем максимальные значения.

Здесь так же добавлено условие: мы обновляем список sm2, если в ячейках sm, на которые опираемся, не ноль (это касается всех троек, кроме первой). Когда анализируем первую тройку во всех ячейках списка sm как раз и должны быть нули.

Зачем мы это делаем ? Дело в том, что ноль в ячейке sm на втором и последующих шагах говорит о том, что мы не получили результата для данного остатка на предыдущем шаге, а значит, от него нельзя отталкиваться.

Это условие можно не писать, когда ищем минимальную сумму. Там после первого шага все нули перезапишутся большими числами из списка sm2. Они не будут порождать результаты, которые смогут соревноваться с реальными суммами по минимальности.

Ответ:

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

Задача (Отработаем навыки)

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на 6 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Пример входного файла:

6
7 2 1
1 3 4
8 5 6
2 8 3
12 3 5
1 4 12

Для указанных входных данных значением искомой суммы должно быть число 48.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение:

Отработаем приём из 27 задания ЕГЭ по информатике.

f=open('27_6b.txt')

n=int(f.readline())

sm = [0]*6

for i in range(n):
    a = f.readline().split()
    x, y, z = int(a[0]), int(a[1]), int(a[2])

    sm2=[0]*6

    for j in range(6):

        r1=sm[j]+x
        r2=sm[j]+y
        r3=sm[j]+z
        
        if i==0 or sm[j]!=0:
            sm2[r1%6] = max(r1, sm2[r1%6])
            sm2[r2%6] = max(r2, sm2[r2%6])
            sm2[r3%6] = max(r3, sm2[r3%6])

    sm=sm2

print(sm[0])

Ответ:

Мы сегодня посмотрели интересный приём, как решать некоторые задачи из ЕГЭ по информатике 27-ого задания. Удачи!

Источник

ЕГЭ информатика 27 задание разбор, теория, как решать.

Создание программы для анализа числовых последовательностей, (В) — 2 балла

Е27.33 В городе M расположена кольцевая автодорога длиной в N километров

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

Е27.32 определить количество таких подпоследовательностей, сумма элементов которых кратна 1111

Дана последовательность натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, состоящие более чем из ста элементов. Необходимо определить количество таких подпоследовательностей, сумма элементов которых кратна 1111. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что число в ответе не …

Е27.31 такие что сумма элементов каждой из них кратна k = 67

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 67. Найдите среди них подпоследовательность с максимальной суммой. Укажите в ответе найденную максимальную сумму. Входные данные Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел …

Е27.30 Необходимо определить количество её непрерывных подпоследовательностей

Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых кратна 999. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел и число в ответе не превышают 2 ∙ 109. Вам …

Е27.29 сумма всех выбранных чисел имела такую же последнюю цифру

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

Е27.28 такие что сумма элементов каждой из них кратна k = 43

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них. Входные данные Даны два входных файла (файл A и …

Е27.27 последовательности, находящихся на расстоянии не меньше чем 5

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

Е27.26 чтобы сумма всех выбранных чисел не делилась на 7

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

Е27.25 чтобы сумма всех выбранных чисел делилась на 4

чтобы сумма всех выбранных чисел делилась на 4. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 4 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую …

Е27.24 Определите максимально возможную сумму всех чисел в третьей группе

Определите максимально возможную сумму всех чисел в третьей группе. Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй – нечётной. Определите максимально возможную сумму всех …

Источник

1. Правильный алгоритм
2. Эффективность.
2.1. Эффективность по времени.
2.2. Эффективность по памяти.
3. Культура оформления программного кода.

Автор статьи — репетитор-профессионал Лада Борисовна Есакова.

Поговорим о задаче 27 (С4) на ЕГЭ по информатике. Она оценивается следующим образом:

— 4 балла, если написанная программа работает верно, она эффективна и содержит до трех синтаксических ошибок;
— 3 балла, если написанная программа работает верно, она не эффективна по памяти (но эффективна по времени), содержит не более пяти синтаксических ошибок и не более одной смысловой ошибки;
— 2 балла, если написанная программа работает верно, но она неэффективна, содержит не более семи синтаксических ошибок и не более двух смысловых ошибок;
— 1 балл, если программа не написана или работает неверно, однако алгоритм решения описан правильно.

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

Давайте выделим основные моменты в решении этой самой сложной задачи.

к оглавлению ▴

1. Правильный алгоритм

До того, как начать программировать, мы должны хорошо понять, что собственно мы собираемся запрограммировать. Причем продумать алгоритм нужно до мелочей, учесть все возможные варианты поведения программы. После этого обязательно подробно и понятно записать алгоритм на простом языке, в виде блок-схемы или в виде таблицы. Кому как удобнее. Это описание будет нашей путеводной нитью при разработке программы. А заодно мы заработаем 1 балл.
Я настойчиво рекомендую подробно описывать алгоритм, даже если Вы уверены в абсолютной правильности программы.

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

к оглавлению ▴

2. Эффективность.

В постановке задачи требуется не просто написать программу, а написать эффективную программу. Давайте разберемся, что же такое эффективность.

Эффективность в данном смысле – это умение экономно расходовать основные ресурсы: память компьютера и время.

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

к оглавлению ▴

2.1. Эффективность по времени.

Наиболее ценным ресурсом в этой задаче считается время. Эффективность по времени расценивается «дороже», чем эффективность по памяти. Как же написать эффективную по времени программу?

Обозначим время выполнения программы T. Допустим, нам нужно последовательно просмотреть в цикле N элементов массива. Тогда время выполнения программы будет прямо пропорционально количеству элементов (T~N).

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

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

Таким образом, нужно стараться избегать вложенных циклов. Это не всегда возможно. Любая сортировка (например, метод пузырька) обязывает нас использовать цикл в цикле.

к оглавлению ▴

2.2. Эффективность по памяти.

Все, что выполняет наша программа, происходит в памяти компьютера.
Объявляя переменные, мы резервируем ячейки памяти (переменная типа Integer занимает в классическом Паскале 2 байта, переменная типа Real – 6 байт).
Записывая введенные данные в массив или переменные, мы используем память.

Поэтому основные приемы экономии памяти:
— Правильно выбирать тип переменной;
— При возможности не сохранять вводимые данные в массив или переменные, а анализировать сразу при вводе;
— Экономно использовать переменные (если возможно, использовать одну переменную для разных целей).
И опять же, позаботьтесь о проверяющем. После написания программы сделайте анализ эффективности. Объясните, почему вы выбрали такие типы переменных. Укажите, где вы экономно использовали одну и ту же переменную в разных целях. Возможно, Вы сознательно уменьшили эффективность по памяти для увеличения эффективности по времени.

к оглавлению ▴

3. Культура оформления программного кода.

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

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

Настоятельно рекомендую выполнять следующие правила, которые не добавят Вам лишний балл, но позитивно настроят проверяющего и застрахуют от возможной недооценки вашей работы:
— Используйте имена переменных, указывающие на их назначение. Например, для обозначения переменной, хранящей максимальную сумму можно использовать наименование maxsum, для массива с номерами школ – schoolnum. Только не переусердствуйте! Под счетчики достаточно ввести переменные i, j…

— Форматируйте текст отступами, обозначая начало-конец программных блоков. Такое форматирование избавит Вас от потери закрывающих скобок и упростит чтение текста;

— Используйте комментарии, коротко описывающие основной смысл происходящего.

Выполнив эти несложные требования, Вы гарантированно получите высший балл за самую сложную задачу ЕГЭ по информатике!

Благодарим за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №27. Написание сложной программы.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из данного раздела.

Публикация обновлена:
08.03.2023

Источник

Что нового?

В предстоящем ЕГЭ не появилось никаких изменений по сравнению с прошлым годом.

Возможно, вам также будут интересны демоверсии ЕГЭ по математике и физике.

О нововведениях в экзаменационных вариантах по другим предметам читайте в наших новостях.

ЕГЭ-2020. Информатика. Тематические тренировочные задания

Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.

Купить

Источник: сайт
ФИПИ

Демоверсия КИМ ЕГЭ-2019 по информатике не претерпел никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще ПРОЕКТА) КИМ ЕГЭ по информатике.

Часть 2

Для записи ответов на задания этой части (24–27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

Далее не видим необходимости придумывать что-то отличное от официального содержания КИМа демоверсии. Этот документ уже несет в себе «содержание верного ответа и указания по оцениванию», а также «указания для оценивания» и некоторые «примечания для эксперта».

Задание 27

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

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

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

В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

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

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

Пояснение. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58·4, 58·1, 58·29, 2·1, 2·29, 3·29. Из них на 29 делятся 5 произведений.

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

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

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

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

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

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

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

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

Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.

При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая четырёх последних. Обозначим их n29.

Примечание для проверяющего. Сами числа, кроме четырёх последних, при этом можно не хранить.

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

Если очередное считанное число делится на 29, то к ответу следует прибавить количество чисел до него, не считая четырёх последних (включая считанное).

Если очередное считанное число на 29 не делится, то к ответу следует прибавить n29.

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

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

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

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

var

n: longint;

a: array[1..s] of longint; {хранение последних s значений}

a_: longint; {очередное значение}

n29: longint; {количество делящихся на 29 элементов, не считая s последних}

cnt: longint; {количество искомых пар}

i, j: longint;

begin

readln(n);

{Ввод первых s чисел}

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

{Ввод остальных значений, подсчет искомых пар}

cnt := 0;

n29 := 0;

for i := s + 1 to n do

begin

if a[1] mod 29 = 0 then n29 := n29 + 1;

readln(a_);

if a_ mod 29 = 0 then cnt := cnt + i — s

else

cnt := cnt + n29;

{сдвигаем элементы вспомогательного массива влево}

for j := 1 to s — 1 do a[j] := a[j + 1];

a[s] := a_ {записываем текущий элемент в конец массива}

end;

writeln(cnt)

end.

Комментарии для проверяющего

1. При таком решении хранятся только последние 4 прочитанных элемента. Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности. Поэтому при увеличении длины последовательности в k раз время работы программы увеличивается не более чем в k раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается в 4 балла.

В такой версии Паскаля, как PascalABC или Delphi, тип longint может быть заменён на тип integer. В большинстве версий языков CC++ также можно использовать тип int.

Программа может быть и ещё более эффективной, если на каждом шаге не сдвигать элементы вспомогательного массива, а записывать i-й считанный элемент в элемент с индексом i mod 4 (Паскаль) или i % 4 (Python), ведя нумерацию обоих индексов с нуля. Учёту подлежит элемент с этим же индексом (именно он находится на расстоянии s от i-го и будет заменён на него). Кроме того, при нумерации индексов элементов с нуля меняется одна из формул для подсчёта.

Такая программа на языке Python приведена ниже (пример 2).

Все подобные программы оцениваются, исходя из максимального балла – 4 (см. критерии).

Вместо последних 4 элементов можно хранить и 4 счётчика: количество делящихся на 29 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних, всех считанных чисел без 3 последних, – и также сдвигать их после очередного шага. Такая программа приведена на языке С++ (пример 3). В этом же примере вместо вспомогательного массива длиной 4 используются 4 переменные.

2. Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив. Такое решение эффективно по времени, но неэффективно по памяти. Оно оценивается, исходя из максимального балла – 3 (см. критерии).

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

Пример 2. Программа на языке Python. Программа эффективна по времени и памяти

s = 4

a = [0]*s

n = int(input())

for i in range(s):

a[i] = int(input())

cnt = 0

n29 = 0

for i in range(s, n):

k = i % s

if a[k] % 29 == 0:

n29 = n29 + 1

a_ = int(input())

if a_ % 29 == 0:

cnt = cnt + i — s + 1

else:

cnt = cnt + n29

a[i % s] = a_

print(cnt)

Пример 3. Программа на языке С++. Программа эффективна по времени и памяти

#include <iostream>

using namespace std;

int main()

{

int s = 4; //требуемое расстояние между элементами

int n;

int n1 = 0, n2 = 0, n3 = 0, n4 = 0;

//хранение последних s счетчиков

int a_; // очередное значение

int cnt; // количество искомых пар

cin >> n;

cnt = 0;

for (int i = 0; i < n; ++i)

{

cin >> a_; // считано очередное значение

if (i >= s)

{

if (a_ % 29 == 0)

cnt += i — s + 1;

else

cnt += n4;

}

//сдвигаем элементы счетчиков

n4 = n3;

n3 = n2;

n2 = n1;

//обновляем счетчик кратных 29

if (a_ % 29 == 0)

n1 += 1;

}

cout << cnt;

return 0;

}

Указания по оцениванию	Баллы
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов
Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, не допустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку	4
Не выполнены условия, позволяющие поставить 4 балла. Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел. Допускается наличие не более одной содержательной (не являющейся синтаксической) ошибки следующих видов: 1) допущена ошибка при вводе данных, например не считывается значение N, или числа могут быть считаны, только если будут записаны в одной строке через пробел; 2) неверная инициализация или её отсутствие там, где она необходима; 3) используется неверный тип данных; 4) использована одна переменная (или константа) вместо другой; 5) используется один знак операции вместо другого; 6) используется одно зарезервированное слово языка программирования вместо другого; 7) неверно используется условный оператор, например else относится не к тому условию; отсутствует вывод ответа, или выводится значение не той переменной; 9) выход за границу массива; 10) неверно расставлены операторные скобки. 3 балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)	3
Пример 4. Программа на языке Паскаль. Программа эффективна по времени и неэффективна по памяти
const s = 4; {требуемое расстояние между элементами} var n: longint; a: array[1..1000] of longint; n29: longint; {количество делящихся на 29 элементов, не считая s последних} cnt: longint; {количество искомых пар} i, j: longint; begin readln(n); {Ввод первых s чисел} for i:=1 to s do readln(a[i]); {Ввод остальных значений, подсчет искомых пар} cnt := 0; n29 := 0; for i := s + 1 to n do begin readln(a[i]); if a[i — s] mod 29 = 0 then n29 := n29 + 1; if a[i] mod 29 = 0 then cnt := cnt + i — s else cnt := cnt + n29; end; writeln(cnt) end.

¹ «Количество информации как степень непредсказуемости», С 170. Ю.А. Быкадоров «Информатика и ИКТ 8»

² «Представление информации в ЭВМ», С 113. Ю.А. Быкадоров «Информатика и ИКТ 10»

³ «Системы логических уравнений: решение с помощью битовых цепочек», К.Ю. Поляков, М.А. Ройтберг, Издательский дом «Первое сентября», Информатика, Декабрь, 2014.

⁴ Или дистрибутивность

#ADVERTISING_INSERT#

Источник

Методика подготовки к сдаче ЕГЭ по информатике (Задача 27)

В задании 27 встречаются несколько типов задач. Рассмотрим их подробнее. В качестве источника задач будем использовать сборник «ЕГЭ 2016 Информатика и ИКТ 20 вариантов» С.С. Крылова и Т.Е.Чуркиной.

Тип задач 1 (делимость).

Вариант 1 по задачнику.

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

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

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

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

Решение.

Следует учитывать, что в задании 27 возможно несколько вариантов решения задачи и их оценивание при правильном решении варьируется от 2 до 4 баллов. От чего зависит результат? От эффективности работы программы. Простейшая программа, которая сохраняет все входные данные в массиве и потом путем обхода этого массива находящая решение оценивается в 2 балла. Если же полученное решение такого, что при росте количества данных, время выполнения и необходимая память растут линейно, то за такую программу экзаменуемый получает 4 балла.

Вернемся к конкретной задаче и сначала рассмотрим самое простое решение.

Алгоритм программы прост.

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

Приведем пример программ, построенных по данному алгоритму, на нескольких языках программирования.

C++

#include

using namespace std;

int main(){

long int mas[1000];

long int N, cryt, temp;

cryt = 0;

cin N;

for (int i=0;i mas[i];

for (i=0;i

for (int j=i+1;j

temp = mas[i]*mas[j];

if (temp%58 == 0) cryt++;

}

cout

}

Python

cryt = 0

mas = []

N = int(input())

for i in range(N):

mas[i] = int(input())

for i in range(N-1):

for j in range(i+1,N):

temp = mas[i]*mas[j]

if temp%58 == 0:

cryt++;

print(cryt)

Теперь рассмотрим вариант решения, эффективного по времени и памяти, на 4 балла.

Когда произведение двух чисел делится на 58?

Когда оба сомножителя делятся на 58.
Только один сомножитель делится на 58.
Одно число делится на 2, другое на 29.

В процессе ввода данных определяем:

— количество чисел, делящихся на 58 – n58;

— количество чисел, делящихся на 2, но не делящихся на 58 – n2;

— количество чисел, кратных 29, но не делящихся на 58 – n29.

После ввода всех данных и вычисления вышеприведенных переменных получаем, что количество пар в группе 1 будет равно n58*(n58-1)/2. В группе 2: n58*(N-n58), где N – общее количество элементов. В группе 3: n2*n29.

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

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

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

C++

#include

using namespace std;

int main(){

long int N, n58, n29, n2, temp, cryt;

n58 = 0;

n29 = 0;

n2 = 0;

cin N;

for (int i=0;i

cin temp;

if (temp%58 == 0) n58++;

else if (temp%29 ==0) n29++;

else if (temp%2 == 0) n2++;

}

crypt = (n58*(n58-1))/2 + n58*(N-n58) +n29*n2;

cout

}

Python

n58 = 0

n29 = 0

n2 = 0

N = int(input())

for i in range(N):

a = int(input())

if temp%58 == 0:

n58++

elif temp%29 ==0:

n29++

elif temp%2 == 0:

n2++

crypt = (n58*(n58-1))//2 + n58*(N-n58) +n29*n2

print(crypt)

Тип задач №2.

Следующий тип задач показан в варианте номер 3 задачника. Здесь мы видим, что изначально дано два разных условия задачи.

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

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

План решения задачи А достаточно прост.

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

Примеры программ на разных языках программирования.

C++

#include

using namespace std;

int main(){

long int mas[6][2];

long int max, temp;

max = 0;

for (int i=0;i mas[i][0] mas[i][1];

for (int i1=0;i1

for (int i2=0;i2

for (int i3=0;i3

for (int i4=0;i4

for (int i5=0;i5

for (int i6=0;i6

temp = mas[0][i1] + mas[1][i2] + mas[2][i3] + mas[3][i4] + mas[4][i5] + mas[5][i6];

if (temp%5 != 0 && max

}

cout

}

Python

max = 0

mas = []

for i in range(6):

mas.append([])

mas[i][0],mas[i][1] = map(int, input().split())

for i1 in range(2):

for i2 in range(2):

for i3 in range(2):

for i4 in range(2):

for i5 in range(2):

for i6 in range(2):

temp = mas[0][i1] + mas[1][i2] + mas[2][i3] + mas[3][i4] + mas[4][i5] + mas[5][i6]

if temp%5 != 0 && max

max = temp;

print(max)

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

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

#include

using namespace std;

int main(){

long int max, max_t, min_t, min_d, temp;

int N;

max = 0;

min_d = 0;

cin N;

for (int i=0;i

cin max_t min_t;

if (min_t max_t){

temp = max_t;

max_t = min_t;

main_t = temp;

}

max += max_t;

temp = max_t – main_t;

if (temp%5 != 0){

if (min_d == 0 || min_d temp) min_d = temp;

}

If (max %5 != 0) cout

else if (min_d 0){

max -= min_d;

cout

} else cout

}

Python

max = 0

N = int(input())

min_d = 0

for i in range(N):

max_t, min_t = map(int, input().split())

if max_t

temp=max_t

max_t=min_t

main_t=temp

max += max_t

temp = max_t – main_t;

if temp%5 != 0 && (min_d == 0 || min_dtemp)):

min_d = temp

if max%5==0:

if min_d0:

max -= min_d

else:

max = 0;

print(max)

Тип задач № 3.

Вариант 6 по задачнику. Является усложнением задачи 2 типа.

Дано.

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

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

Решение.

Задача А решается аналогично задаче А второго типа.

Примеры решения.

C++

#include

using namespace std;

int main(){

int mas[5][3];

long int min, temp;

min =0;

for (int i=0;i mas[i][0] mas[i][1] mas[i][2];

for (int i1=0;i1

for (int i2=0;i2

for (int i3=0;i3

for (int i4=0;i4

for (int i5=0;i5

temp = mas[0][i1]*mas[0][i1] + mas[1][i2]* mas[1][i2] + mas[2][i3]* mas[2][i3] + mas[3][i4] + mas[4][i5]* mas[4][i5];

if (temp%2 == 0){

if (min ==0) min = temp;

if (min temp) min = temp;

}

cout min endl;

}

Python

min = 0

mas = []

for i in range(5):

mas.append([])

mas[i][0],mas[i][1],mas[i][2] = map(int, input().split())

for i1 in range(3):

for i2 in range(3):

for i3 in range(3):

for i4 in range(3):

for i5 in range(3):

temp = mas[0][i1] + mas[1][i2] + mas[2][i3] + mas[3][i4]+ mas[4][i5]

if temp%2 == 0 && max

max = temp;

print(max)

Задача Б.

За основу необходимо взять решение задачи Б 2 типа с некоторыми изменениями.

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

Примеры программ.

С++

#include stdlib.h

#include

function comp_up(const void * a, const void * b){

return(*(long int*) a — *(long int*) b);

}

using namespace std;

int main(){

long int mas[3];

int N;

long int min, temp, min_d;

min = 0;

min_d = 0;

cin N;

for (int i=0;i

cin mas[0] mas[1] mas[2];

qsort(mas, 3, sizeof(long int), comp_up);

min += mas[0]*mas[0];

temp = mas[1]*mas[1]-mas[0]*mas[0];

if (temp%2 != 0){

if (min_d == 0 || min_d temp) min_d = temp;

} else{

temp = mas[2]*mas[2]-mas[1]*mas[1];

if ((temp%2 !=0)&&(min_d == 0 || min_d temp)) min_d = temp;

}

If (min%2 != 0){

If (min_d0) min +=min_d; else min = 0;

}

cout

}

Python

min = 0

min_d = 0;

mas = []

N = int(input())

for i in range(N):

mas[0], mas[1], mas[2] = map(int, input().split())

mas.sort()

min += mas[0]*mas[0]

temp = mas[1]*mas[1]-mas[0]*mas[0]

if temp%2 != 0:

if min_d == 0 || min_d temp:

min_d = temp

else:

temp = mas[2]*mas[2]-mas[1]*mas[1]

if (temp%2 !=0)&&(min_d == 0 || min_d temp):

min_d = temp

If min%2 != 0:

If min_d0:

min +=min_d

else:

min = 0;

print(min)

Тип задач №4 (очередь).

Вариант 13 по задачнику.

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

Необходимо найти в заданной серии показаний датчика минимальное четное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удается, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

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

Б. Напишите программу, которая будет эффективной по времени и по памяти.

Решение.

Задача А.

Алгоритм решения задачи.

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

Примеры программ.

C++

#include

using namespace std;

int main(){

int mas[10000], N;

long int min, temp;

min = -1;

cin N;

for (int i=0;i mas[i];

for (i=0;i

for (int j=i+15;j

temp = mas[i]*mas[j];

if ((temp%2==0)&&(min==-1 || mintemp)) min = temp;

}

cout

}

Python

mas = []

min = -1

N = int(input())

for i in range(15):

mas[i] = int(input())

for i in range(N-15):

for j in range(i+15,N):

temp = mas[i]*mas[j]

if (temp%2==0)&&(min==-1 || mintemp):

min = temp

print(min)

Задача Б.

Для решения этой задачи необходимо организовать хранение и обработку временно неиспользуемых значений. Лучше всего для этого подходит очередь или FIFO (First In First Out). Далеко не во всех языках программирования работа с такой структурой реализована на уровне стандартной библиотеки.

Алгоритм решения задачи достаточно прост.

Нам будут необходимы две вспомогательные переменные. Одна из них будет хранить минимальное четное значение вне 15 секундного диапазона, другая – просто минимальное значение вне 15 сек диапазона.

Сначала наполняем очередь первыми 15 значениями.
Вынимаем из очереди первый зашедший элемент и используем его для определения минимального значения вне 15 сек зоны и, если элемент четный — то и минимального четного вне 15 сек зоны.
Считываем новое значение.
Если оно четное, то перемножаем его с минимальным значением вне 15 сек зоны, иначе с минимальным четным значением вне 15 сек зоны.
Полученное значение сравниваем с минимальным четным значением. При необходимости обновляем минимум.
Помещаем ранее считанное значение в конец очереди.
Если еще есть значения, то переходим к пункту 2.
Выводим результат на печать.

Примеры программ.

C++

#include

using namespace std;

int main(){

queue mas;

int N, a;

long int min, min_out15_even, minn_out15, temp;

cin N;

for (int i=0;i

cin a;

mas.push(a);

}

min = -1;

min_out15_even = 0;

min_out15 = 0;

for (i=0;i

a = mas.pop();

if ((a%2==0)&&(min_out15_even==0 || a

if (min_out15==0 || a

cin a;

mas.push(a);

if (a%2==0) temp=min_out15*a;

else temp=min_out15_even*a;

if (min==-1 || mintemp) min = temp;

}

cout

}

Python

from queue import Queue

mas = Queue()

N = int(input())

for i in range(15):

a = int(input())

mas.put(a)

min = -1

min_out15_even = 0

min_out15 = 0

for i in range(N-15):

a = mas.get()

if (a%2==0)&&(min_out15_even==0 || a

min_out15_even = a

if min_out15==0 || a

min_out15 = a

a = int(input())

mas.put(a)

if a%2==0:

temp=min_out15*a

else:

temp=min_out15_even*a

if min==-1 || mintemp:

min = temp

print(min)

Тип задач №5 (исключения).

Вариант 17 в задачнике.

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

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

Требуется написать эффективную по времени и памяти программу.

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

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

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

Считываем данные, попутно определяя:

а) номер элемента с нулевым С-индексом;
б) количество элементов с нечетным С-индексом ;
в) номер элемента с минимальным нечетным С-индексом.

2. Выводим номера всех элементов от 1 до N за исключением номеров вышеуказанных элементов.

Примеры программ.

#include

using namespace std;

int main(){

int a, i_0, i_min_odd, min_odd, odd_cnt;

min_odd = -1;

i_min_odd = 0;

i_0 = 0;

odd_cnt = 0;

cin N;

for (int i=1;i

cin a;

if (a==0) i_0=i;

if (a%2 != 0){

odd_cnt++;

if (min_odd==-1 || min_odd a){

min_odd = a;

i_min_odd = i;

}

for (int i=1;i

if (i != i_0 && !(cnt_odd%2 !=0 && i_min_odd==i)) cout

}

Python

min_odd = -1

i_min_odd = 0

i_0 = 0

odd_cnt = 0

N = int(input())

for i in range(1,N+1):

a = int(input())

if a==0:

i_0=i;

if a%2 != 0:

odd_cnt++

if min_odd==-1 || min_odd a:

min_odd = a

i_min_odd = i

for i in range(1,N+1):

if i != i_0 && !(cnt_odd%2 !=0 && i_min_odd==i):

print(I, “ “)

Источник

Автор: учитель информатики Шахова Е.А., г. Севастополь, ГБОУ «Гимназия №1 им. А.С. Пушкина».

Задача №27 в ЕГЭ является задачей высокого уровня, призванная , прежде всего, проверить умения учащихся на практике составлять и реализовывать эффективные и правильные алгоритмы, составлять программы на языках высокого уровня.

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

Характеристика	Значение
Что проверяется	Умение создавать собственные программы (30–50 строк) для решения задач средней сложности
Требования к проверяемым элементам содержания	Основные этапы разработки программ. Разбиение задачи на подзадачи.
Проверяемые требования к уровню подготовки	Создавать программы на языке программирования по их описанию
Уровень сложности	Высокий
Максимальный балл	4
Примерное время выполнения	55 мин

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

Проанализируем результаты решения этой задачи в 2015-2016 учебном году. Процент выполнения этой задачи представлен в следующей таблице:

Полученные баллы	1	2	3-4	>0
Процент участников	7%	3,7%	5,7%	16,2%

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

Итак, как же научиться решать эти задания?

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

понятие сложности алгоритма;

объявление, ввод массива;

записи (структуры данных);

работа со строками и символьными переменными;

нахождение максимума и минимума в массиве, в последовательности;

нахождение суммы, произведения элементов массива, последовательности;

свойства кратности, делимости сумм и произведений чисел;

сдвиг элементов массива;

использование вложенных циклов для полного перебора.

В качестве особенностей решения задачи можно выделить следующие:

большое количество возможных вариаций задач и их формулировок;

от учащегося требуются хорошие практически навыки программирования;

требуется знать свойства делимости;

большое количество приемов и способов решения, которые трудно формализовать;

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

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

Сложность алгоритмов

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

Основные ресурсы:

время (временнáя сложность) и

объем памяти (ёмкостная сложность).

Наиболее важной характеристикой является время.

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

Различаютсложность в худшем случае и сложность в среднем.

В теории сложности чаще оперируют понятием сложности в худшем случае.

Обычно оценивают порядок роста сложности приn®¥:T = O(f(n)).

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

Именно порядок роста сложности ограничивает размер решаемых задач.

Например, если сравнивать порядок зависимости времени решения задачи, можно привести данные, представленные в таблице:

Выделим основные типы и темы заданий:

Обработка данных, вводимых в виде символьных строк или последовательности чисел.

Проверка контрольного значения среди последовательности чисел.

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

Выбор подмножества элементов с определенным набором свойств.

Выбор одного значения из пары с нахождением суммы или произведения с определёнными свойствами.

Рассмотрим каждый тип задачи отдельно.

Возможная формулировка задания (тип I)

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат:

<Фамилия><Инициалы><номер школы>

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер.<Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.

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

Необходимые знания и умения:

Решение задачи разбиения строки на подстроки по пробелам.

Функцииипроцедуры (Pascal) : pos, copy, delete, length, insert.

Преобразование строки в число, в цифры.

Функцииипроцедуры (Pascal) : val, StrToInt (Delphi).

Работа с символами. Функции (Pascal): ord, chr.

Работа с записями (структурами).

Type Rec=record

{поля записи}

F:string[20]; {фамилия}

IO: string[4]; {инициалы}

num: integer;{номершколы}

end;

Подробно останавливаться не будем из-за неактуальности.

Возможная формулировка задания (тип II)

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

1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R — нечётное число.

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

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

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

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

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

100

145

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

145

Рассмотрим неоптимальное решение полным перебором, которое оценивается в 2 балла.

Организация полного перебора

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

Текстпрограммы (авторский).

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-1 do

for j:=i+1 to n do

begin

R:=a[i]+a[j];

{проверка условия контрольного значения}

if (R<Rmin)and(R mod 3=0) thenRmin:=R;

end;

if Rmin=2001 then Rmin:=-1;

writeln(Rmin);

End.

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

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

Как видно, для данного типа задач можно подготовить шаблонное неоптимальное решение на 2 балла.

Рассмотрим поиск оптимальным способом, т.е. без использования массива для хранения всех данных.

Оптимальное решение.

Если не хранить все числа, то тогда во время ввода данных какие именно хранить?

ИДЕЯ: Хранить в памяти не все введенные ранее числа, а только те, которые «лучше» остальных.

Чтобы сумма была меньше, нужно брать меньшие числа, достаточно хранить только минимальные, удовлетворяющие условию.

Сколько таких чисел хранить и какие должны быть условия?

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

Вывод: следует хранить все минимальные числа, имеющие разные остатки при делении на 3.

Попытаемся словесно сформулировать алгоритм решения. Назовем парным остатком такой остаток, который в сумме с текущим будет делиться на 3.

Алгоритм оптимального решения

Считываем количество чисел n.

Инициализируем переменные.

Цикл из n итераций

Чтение очередного числа a.

Вычисление его остатка от деления на 3.

Выбираем число, остаток от деления на 3 от которого в сумме с остатком деления a на 3 кратен 3 (парный).

Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.

Если число a меньше минимального, имеющего тот же остаток от деления на 3, запоминаем его.

Если контрольное число не изменилось, запоминаем в него 1.

Вывод контрольного значения.

Программа для оптимального решения

Var R, Rmin:integer;

n, a, I,m1,m2:integer;

b : array[0..2] ofinteger; {массив, хранящий минимальные значения с разными остатками при делении на 3.}

Begin

Rmin:=2001;

for i:=0 to 2 do b[i]:=1001; // заполняем массив «невозможными» числами

readln(n);

for i:=1 to n do

begin

readln(a);

m1:=(amod 3);//смотрим остаток от деления на 3

m2:=( 3-m1)mod 3;//смотрим парный остаток от деления на 3

ifb[m2]<>1001then

begin R:=a+b[m3]; {читаем сумму текущего элемента с минимальным, имеющим парный остаток}

if R<Rmin then

Rmin:=R;

end;

{проверяем, не является ли текущий элемент лучше предыдущего, имеющего такой же остаток }

if a<b[m1] then

b[m1]:=a;

end;

if Rmin=2001then Rmin:=-1; //если сумма не нашлась такая

writeln(Rmin);

End.

Как мы видим, что алгоритм сложнее, но, тем не менее, тоже может быть формализован.

Возможная формулировка задания (тип III)

Для заданной последовательности неотрицательных целых чисел необходимо найти минимальную сумму двух её элементов, номера которых различаются не менее чем на 4. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

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

Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

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

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности. Гарантируется, что N > 4. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности. Программа должна вывести одно число – описанную в условии сумму.

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

245

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

Решение задачи А (не оптимальное)

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

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-4 do

for j:=i+4 to n do

begin

R:=a[i]+a[j];

if (R<Rmin) then {проверка условия контрольного значения}

Rmin:=R;

end;

writeln(Rmin);

End.

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

Оптимальное решение

Намного интереснее найти оптимальное решение. Как всегда нужно сформулировать идею.

Рассмотрим следующую последовательность:

Зеленым изображено очередное введенное число, голубыми те числа, с которыми оно может составлять пару, красными – с которыми не может, потому как их индексы отличаются меньше, чем на 4.

Если нельзя хранить все введенные ранее числа, то сколько чисел хранить в памяти и какие?

Во-первых, необходимо хранить числа — «кандидаты» в лучшие для составления с новым полученным числом контрольного значения. Эти числа были получены как минимум за 4 (согласно условию задачи) числа до текущего. В текущем примере это только число 4, которое минимально из всех предыдущих чисел.

Во-вторых, необходимо хранить предпоследние 3 числа, которые пока не могут быть использованы для формирования контрольного значения, но могут пригодиться для последующих чисел. В данном случае мы видим, что в красной зоне есть числа 3 и 1, которые меньше 4, и для будущих чисел могут составить лучше пару, но пока еще использоваться не могут.

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

Сформулируем алгоритм решения.

Алгоритм решения задачи Б

Считываем количество чисел n.

Инициализация переменных, считываем первое число, сохраняем как лучшее.

Считываем 3 числа, запоминаем в массив.

Цикл из n-4 итераций

Чтение очередного числа a.

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

Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее.

Сдвигаем влево на 1 элементы массива.

Запоминаемa в последний элемент массива.

Вывод контрольного значения.

Программа для решения задачи Б

Const delta=4; {минимальный интервал}

Var R :integer; {минимальная сумма}

n,a, m:integer;{количество чисел, очередное значение, лучшее}

b :array[1..delta-1]of integer; {массив промежуточных значений}

Begin

R:=2001;

readln(n);

readln(m); {читаем первое, считаем его «лучшим»}

{ Считываем 3 числа, запоминаем в массив }

for i:=1 to delta-1 do readln(b[i]);

for i:= delta+1 to n do

begin{ Чтение очередного числа a}

readln(a);

{Складываем с лучшим. Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.}

If (m+a)<R then R:=a+m;

{Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее}

if b[1]<m then m:=b[1];

{Сдвигаем влево на 1 элементы массива}

for j:=1 to delta-2 do b[j]:=b[j+1];

{Запоминаем a в последний элемент массива}

b[delta-1]:=a;

end;

writeln(R);

End.

Модификация задачи (тип III)

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

Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Можно заметить, что задача очень похожа на предыдущую, но появляется дополнительное условие, а именно необходимость кратности пяти произведения. Получается некий симбиоз задачи типа II и типа III. Объединим идеи.

Решение задачи А (не оптимальное)

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R :longint;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=1000001;

for i:=1 to n-6 do

for j:=i+6 to n do

begin

R:=a[i]+a[j];

if(R<Rmin) and (R mod 5 =0) then

Rmin:=R;

end;

if Rmin=1000001 then

Rmin:=0;

writeln(Rmin);

End.

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

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

Программа для решения задачи Б

Const delta=6; {минимальный интервал}

Var R :longint ; {минимальное произведение}

n, a:integer; {количество чисел, очередное значение}

m, m5:integer; {наименьшее, наименьшее из кратных 5}

b :array[1..delta-1]of integer; {массив промежуточных значений}

Begin

R:=1000001;

readln(n);readln(m);

if (m mod 5)=0 then

m5:=m

else

m5:=0;

for i:=1 to delta-1 do

readln(b[i]);

for i:= delta+1 to n do

beginreadln(a);

{проверяем произведение с наименьшим, кратным 5}

if ((m5<>0) and ((m5*a)<R) then

R:=a*m5;

{проверяем произведение с наименьшим и чтобы оно было кратно 5}

if ((a mod 5)=0) and (a*m<R)) then

R:=a*m;

{проверяем, не является ли 1-е число в массиве наименьшим и наименьшим, кратным 5}

if b[1]<m then

m:=b[1];

if (b[1]mod 5=0) and (b[1]<m5) then

m5:=b[1];

{сдвиг в массиве}

for j:=1 to delta-2 do b[i]:=b[i+1];

b[delta-1]:=a;

end;

if Rmin=1000001 then Rmin:=0;

writeln (Rmin);

End.

Возможная формулировка задания (тип IV)

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

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

При данной формулировке задачи проще сразу рассмотреть оптимальное решение.

Поскольку задачу нужно решать в один проход (если делать оптимальное решение), то сумму надо считать одновременно с чтением данных.

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

Вывод: нужно брать все положительные элементы и не брать нулевые.

Проблема 2: не все числа должны входить в эту сумму, чтобы она была нечетной.

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

Текст оптимального решения представлен ниже.

Программа оптимального решения

Var s: longint ;{сумма}

n,a:integer;{количество чисел, очередное значение}

m :integer;{наименьшее нечетное}

Begin

S:=0;

readln(n);

m:=0;

for i:= 1 to n do

begin

readln(a);

S:=s+a;

if ( (a mod 2)=1) and ((m=0) or (a<m)) then

m:=a;

end;

if (s mod 2)=0 then

s:=s-m;

writeln(R);

End.

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

Возможная формулировка задания (тип V)

На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 6 и при этом была минимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются за ту из подзадач, что решена на большее количество баллов. Задача А дает 2 балла, задача Б — 4 балла. В задаче А приведите неэффективный алгоритм. При решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по времени ИЛИ памяти, дается 3 балла, по времени И памяти — 2 балла.

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

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

5 4

3 2

1 1

18 3

11 12

2 5

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

Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

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

5 4

3 2

1 1

18 3

11 12

2 5

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

Полный перебор представляет собой вложенные циклы для перебора всех возможных пар значений.

РешениезадачиА

Var a:array[1..6,1..2]of integer;

i,j1,j2,j3,j4,j5,j6,s,smin: integer;

Begin

for i:=1 to 6 do

for j1:=1 to 2 do

read(a[I,j1]);

smin:=1000*6+1;

for j1:=1 to 2 do

for j2:=1 to 2 do

for j3:=1 to 2 do

for j4:=1 to 2 do

for j5:=1 to 2 do

for j6:=1 to 2 do

begin

s:=a[1,j1]+ a[2,j2] +a[3,j3]+ a[4,j4]+ a[5,j5] +a[6,j6];

if (s<smin) and (s mod 6 <>0) then smin:=s

end;

if smin= 1000*6+1 then smin:=1;

writeln(smin);

End.

Идея решения задачи Б

Проблема 1: сумма должна быть минимальной по значению.

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

Проблема 2: Сумма может получиться кратной 6.

Вывод: надо запоминать «кандидатов» на замену одного числа из пары на другое, если сумма вдруг получится кратной 6. Число должно иметь, во первых, минимальную разницу с заменяемым, а во-вторых, должно иметь другой остаток при делении на 6, чтобы и сумма поменяла свой остаток от деления. Сумма при этом увеличится именно на разницу между числами, поэтому проще запоминать именно ее.

Ниже приведен полный текст решения задачи.

Решение задачи Б

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

a, b : integer; {очередная пара чисел}

dmin,d : integer; {минимальная разница между числами в паре}

s:integer; i:integer;

Begin

readln(n);

s:=0; d:=1001;

for i:=1 to n do

begin

readln(a,b);

{добавляем минимальное число в сумму}

if a <b then

s:=s+a

else

s:=s+b;

{вычисляем разницу между числами}

d:=abs(a—b);

{если разница минимальна и не кратна 6, запоминаем ее}

if (d<dmin)and(d mod 6 <>0) then

dmin:=d;

end;

{если сумма получилась кратной 6, увеличиваем ее на dmin}

If (s mod 6) =0 then

If dmin=1001 then

s:=0

else

s:=s+dmin;

writeln(s);

end.

Список использованных источников

В.Р. Лещинер, М.А. Ройтберг. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ для учителей, подготовленные на основе анализа типичных ошибок Участников ЕГЭ 2016 года по ИНФОРМАТИКЕ и ИКТ. –http://www.fipi.ru/ege—i—gve-11/analiticheskie—i—metodicheskie—materialy.

КИМ ЕГЭ «Информатика и ИКТ»http://www.ege.edu.ru/ru/classes-11/preparation/demovers/

Материалы сайта Полякова К.Ю. по подготовке к ЕГЭhttp://kpolyakov.spb.ru/school/ege.htm.

Информатика и ИКТ. Подготовка к ЕГЭ 2016. 20 тренировочных вариантов по демоверсии на 2016 год: учебно-методическое пособие./Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов на Дону: Легион, 2015.

Каталог заданий сайта «Решу ЕГЭ». –

https://inf—ege.sdamgia.ru/test?a=catlistwstat

Источник

Решение 27 заданий ЕГЭ по информатике

Задания 2021 и более поздние

Задания предыдущих лет на повторение

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

Выбрать из каждой пары одно число

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

Анализ пар, находящихся на расстоянии

Е27.33 В городе M расположена кольцевая автодорога длиной в N километров

Е27.32 определить количество таких подпоследовательностей, сумма элементов которых кратна 1111

Е27.31 такие что сумма элементов каждой из них кратна k = 67

Е27.30 Необходимо определить количество её непрерывных подпоследовательностей

Е27.29 сумма всех выбранных чисел имела такую же последнюю цифру

Е27.28 такие что сумма элементов каждой из них кратна k = 43

Е27.27 последовательности, находящихся на расстоянии не меньше чем 5

Е27.26 чтобы сумма всех выбранных чисел не делилась на 7

Е27.25 чтобы сумма всех выбранных чисел делилась на 4

Е27.24 Определите максимально возможную сумму всех чисел в третьей группе

1. Правильный алгоритм

2. Эффективность.

2.1. Эффективность по времени.

2.2. Эффективность по памяти.

3. Культура оформления программного кода.

Часть 2

Задание 27

Возможная формулировка задания (тип I)

Возможная формулировка задания (тип II)

Организация полного перебора

Алгоритм оптимального решения

Программа для оптимального решения

Возможная формулировка задания (тип III)

Решение задачи А (не оптимальное)

Алгоритм решения задачи Б

Программа для решения задачи Б

Модификация задачи (тип III)

Решение задачи А (не оптимальное)

Программа для решения задачи Б

Возможная формулировка задания (тип IV)

Программа оптимального решения

Возможная формулировка задания (тип V)

РешениезадачиА

Решение задачи Б

Новое и интересное на сайте: