Последнее задание егэ по информатике

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

Решить 27 задание из ЕГЭ по информатике очень важно, ведь оно самое трудное, и за него дают, как правило, больше всего вторичных баллов.

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

Задача (Демонстрационный вариант 2021)

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

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

Входные данные.

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

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

6
1 3
5 12
6 9
5 4
3 3
1 1

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

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

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

Решение:

Напишем программу на языке программирования Pascal ABC для решения этого 27 задание из Демонстрационного варианта ЕГЭ по информатике.

var
  f: text;
  i, sum, min_range, x, y, n: integer;
 
begin
  assign(f, 'c:27-A.txt');
  reset(f);
  
  read(f, n);
  
  min_range:=10001;
  sum:=0;
  
  for i:=1 to n do begin
    read(f, x);
    read(f, y);

    if x>y then 
      sum:=sum+x
    else
      sum:=sum+y;

    if (abs(x-y) < min_range) and (abs(x-y) mod 3 <> 0) then
       min_range := abs(x-y);
  end;
    
  if sum mod 3 <> 0 then Writeln(sum)
    else Writeln(sum-min_range);
  
end.

В начале считаем левый столбик чисел в массив m, а правый столбик в массив k.

Найдём максимальную сумму в переменную sum. В переменной min_range мы будем хранить минимальную разницу между парой чисел, которая НЕ делится на 3.

Идея задачи следующая: Если максимальная сумма делится на 3, то мы должны отнять переменную min_range от максимальной суммы. Это означает, что мы заменили какой-то элемент суммы. При этом новое значение точно не будет делиться на 3, ведь min_range — Не делится на 3! Плюс min_range — это минимальная разница между числами, а значит, сумма будет максимально возможной.

Не забудьте заменить при обработке файла 27-A.txt значение для константы n на 20.

Ответ:

Решим ещё одну примерную задачу из 27 задания ЕГЭ по информатике.

Задача (Тройки чисел)

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

Входные данные:

Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

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

Источник: https://inf-ege.sdamgia.ru/

Решение:

Запрограммируем задачу на языке программирования Pascal ABC.

var
  f: text;
  i, n, sum1, sum2, sum3, min_range, min, x, y, z: integer;

begin
  assign(f, 'c:27-B.txt');
  reset(f);
  
  read(f, n);
  
  sum1:=0;
  sum2:=0;
  sum3:=0;
  
  min_range:=10001;

  for i:=1 to n do begin
    
    read(f, x);
    read(f, y);
    read(f, z);
  
    min:=x;
    
    if y < min then min:=y;
    if z < min then min:=z;
    
    sum1:=sum1+min;
    
    if (x=min) then begin    
      sum2 := sum2 + y;
      sum3 := sum3 + z;    
    end else begin
    
        if (y=min) then begin    
          sum2 := sum2 + x;
          sum3 := sum3 + z;    
        end else begin
    
            if (z=min) then begin    
              sum2 := sum2 + x;
              sum3 := sum3 + y;    
            end;

        end; 

    end;
    
    if (x <> min) and (x-min < min_range) and ((x - min) mod 2 <> 0) then 
      min_range := x-min;
    
    if (y <> min) and (y-min < min_range) and ((y - min) mod 2 <> 0) then 
      min_range := y-min;
    
    if (z <> min) and (z-min < min_range) and ((z - min) mod 2 <> 0) then 
      min_range := z-min;
    
  end;
  
    if (sum2 + sum3) mod 2 <> 0 then
        writeln(sum1)
    else writeln(sum1 + min_range);

end.

В переменную sum1 мы будем суммировать минимальное число из каждой тройки. В переменные sum2 и sum3 суммируем оставшееся числа из тройки (Порядок будет не важен). В переменной min_range получим минимальную разницу между минимальными значениями и оставшимися числами из каждой тройки, причём, эта разница должна быть нечётная.

Ключевой момент: Если сумма одного столбца будет чётной, а второго столбца — нечётной, то сумма этих двух столбцов будет нечётной.

Пример: 5+8=13, 13+4=17 и т.д. Наоборот: 4+6=10, 3+3=6.

Если у нас такая ситуация будет, тогда достаточно распечатать переменную sum1 (Т.е. тот столбец, где находятся минимальные числа).

Если ситуация будет другая, то достаточно заменить числа в той паре, которая дала нам переменную min_range. Тогда сумма в sum1 возрастёт на значение min_range.

Т.к. значение переменной min_range является нечётным, то после замены, sum2+sum3 — будет нечётной, что означает, что одно значение будет чётным, а другое нечётное.

Ответ:

Рассмотрим задачу с популярного сайта по информатике К.Ю. Полякова.

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

(№ 2683) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел НЕ оканчивалась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

6
3 5
5 12
6 9
5 4
7 9
5 1

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

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

Источник: https://kpolyakov.spb.ru/

Решение:

Задача похоже на демонстрационный вариант из ЕГЭ по информатике 2021.

var
  f: text;
  i, sum, min_range, x, y, n: integer;

begin
  assign(f, 'c:27-23b.txt');
  reset(f);
  
  read(f, n);
  
  min_range:=10001;
  sum:=0;
  
  for i:=1 to n do begin
    read(f, x);
    read(f, y);

    if x>y then 
      sum:=sum+x
    else
      sum:=sum+y;

    if (abs(x-y) < min_range) and (abs(x-y) mod 10 <> 0) then
       min_range := abs(x-y);
  end;
    
  if sum mod 10 <> 5 then Writeln(sum)
    else Writeln(sum-min_range);
  
end.

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

Ответ:

12 задание ЕГЭ по информатике обычно решает только половина выпускников. Оно правда такое сложное? Нет, если заранее изучить каждый из трех прототипов. Из этой статьи вы узнаете, как справиться с Редактором, Роботом и Чертежником — и как можно сделать это еще проще, используя программирование.

Прототипы задания 12 и их сложности

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

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

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

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

Робот — прототип на работу с клетчатой плоскостью и алгоритмом. Вам дают алгоритм и плоскость, содержащую 36 клеток. Нужно найти количество клеток, удовлетворяющее определенному условию. Сложность в том, что ученики начинают проверять все 36 клеток. Делать это не нужно, если проанализировать алгоритм из условия.

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

Редактор — как решать?

Задания с прототипом «Редактор» можно решать как аналитически, так и с помощью компьютера, если у вас все хорошо с программированием. Мы рассмотрим с вами оба способа решения и убедимся, что они дают одинаковые ответы.

Пример 1 (Редактор)

Исполнитель Редактор получает на вход строку цифр и преобразовывает ее.

Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 88 идущих подряд цифр 4? В ответе запишите полученную строку.

Аналитическое решение

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

Сначала уберем по возможности все четверки из цепочки.

88 / 3 = 29 и 1 в остатке. 

Получается, что из цепочки уйдет 29 блоков по 3 четверки и образуется 29 единиц, 1 четверка останется в цепочке в самом конце.

Теперь будем последовательно убирать единицы из цепочки.

29 “1” + 1 “4”

1 “4” + 27 “1” + 1 “4”

2 “4” + 25 “1” + 1 “4”

3 “4” + 23 “1” + 1 “4”

24 “1” + 1 “4”

Как только в цепочке появились 3 четверки, алгоритм заменил их назад на единицу. Суммарно из цепочки ушло 5 единиц. Это действие будет повторяться циклически, поэтому можно посчитать, сколько блоков по 5 единиц уйдет из цепочки.

29 / 5 = 5 и 4 в остатке

Получается, что в цепочке останется 4 единицы и 1 четверка.

11114 → 4114 → 444 → 1

В итоге в цепочке останется только единица.

Решение с помощью компьютера 

В самом задании у нас уже написана программа. Остается перевести ее на конкретный язык программирования. Напишем программу на Python.

Она будет выглядеть следующим образом:

Создаем строку, содержащую 88 четверок. Далее запускаем цикл, который будет проверять, есть ли в строке 3 четверки или 2 единицы. Пропиваем условие и замену в строке. Важно в методе replace() указать третий параметр, который отмечает, сколько замен нужно выполнить. По умолчанию replace() сразу заменит все цифры в строке, а нам нужно выполнять замены по одной.

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

Ответ: 1

Пример 2 (Редактор)

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)     нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

На вход приведенной ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 25 цифр 1, 45 цифр 2 и 10 цифр 3, расположенных в произвольном порядке.

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

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

Аналитическое решение 

Цифры 1, 2 и 3 находятся в строке в произвольном порядке. Все, что нам нужно сделать, чтобы получить ответ — это понять, сколько цифр образовалось в результате замен. 

Каждую единицу алгоритм заменит на тройку. Если изначально было 25 единиц, то в результате замен образуется 25 троек, и их сумма будет равна 25 * 3 = 75.

Каждую двойку алгоритм заменит на 2 единицы. Изначально было 45 двоек, значит, в результате замен образуется 90 единиц. Их сумма будет равна 90.

Каждую тройку алгоритм заменит на 2 тройки. Было 10 троек, станет 20. Сумма составит 20 * 3 = 60.

Итоговая сумма всех цифр цепочки будет равна 75 + 90 + 60 = 225.

Решение с помощью компьютера

Перенесем алгоритм на язык программирования Python.

Получаем следующую программу:

Сначала мы задали строку, содержащую знак “>” и нужное количество всех цифр. Далее в цикле проверяем наличие знака “>” и цифр и выполняем замену. Как только программа вышла из цикла, считаем количество единиц, двоек и троек в строке — и находим сумму. При запуске программы также получается ответ 225.

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

Ответ: 225

Робот — как решать?

Второй прототип, который включает в себя 12 задание ЕГЭ по информатике — Робот. Этот прототип точно придётся решать аналитически, поэтому давайте разбираться, как сделать это с минимальными затратами времени.

Пример 3 (Робот)

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. 

Команды-приказы: вверх, вниз, влево, вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервется.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно

Цикл

ПОКА < условие > команда

Выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Если РОБОТ начнет движение в сторону стены, то он разрушится, и программа прервется. 

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?

НАЧАЛО

ПОКА < снизу свободно > вправо

ПОКА < справа свободно > вверх

ПОКА < сверху свободно > влево

ПОКА < слева свободно > вниз

КОНЕЦ

Решение

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

Проверяем по алгоритму 12 отмеченных клеток. 

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

Ответ: 1

Прототип Чертежник — как решать?

Последний прототип, который составители включили в 12 задание ЕГЭ по информатике — это Чертежник. Здесь при решении важно правильно составить систему уравнений и найти наибольший/наименьший делитель двух чисел. Посмотрим, как это сделать.

Пример 4 (Чертежник)

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).

Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

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

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

Решение

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

Далее составим систему уравнений. Нам известно, как перемещался Чертежник, и сказано, что он вернулся в начальную точку. Получается, его перемещение равно 0.

Теперь мы можем найти n — наибольшее количество повторений цикла. Число n должно быть делителем как 24, так и 16, то есть нам нужно найти НОД(24, 16). Он равен 8. Это и будет ответом к заданию.

Ответ: 8

Что нужно запомнить?

1. Если вам попадется Редактор, можете написать программу, которая найдет ответ вместо вас. Но всегда рассчитывайте, что будет рациональнее: аналитическое решение или компьютерное. Если останется время, можно проверить себя вторым способом.
2. Решая задание с Роботом, не нужно проверять все клетки — это долго. Проанализируйте алгоритм и проверяйте только те клетки, которые действительно могут подойти под условия.
3. Чтобы разобраться с Чертежником, внимательно составляйте систему уравнений. Ищите НОД, если нужно найти наибольшее количество повторений цикла. 
4. Если в конце экзамена осталось время, вернитесь к заданию и проверьте его — ребята часто теряют баллы из-за невнимательности. Особенно рекомендую перепроверить Робота — решите его заново. 

Теперь вы знаете, как решать 12 задание ЕГЭ по информатике! Обязательно прочитайте наш гайд по этому экзамену, если хотите разобраться с остальными темами и заданиями. Там вы найдете структуру экзамена, актуальные прототипы, тематические блоки и лайфхаки от наших преподавателей. Желаем удачи в подготовке 🙂