Блог по программированию

Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

ЕГЭ по информатике 2021 - Задание 27 (Заключительное)



Привет! Сегодня мы рассмотрим последнее 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.



Ответ:
127127399762080




Решим ещё одну примерную задачу из 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;
    
    if (y=min) then begin    
      sum2 := sum2 + x;
      sum3 := sum3 + z;    
    end;
    
   if (z=min) then begin    
      sum2 := sum2 + x;
      sum3 := sum3 + y;    
    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 - будет нечётной, что означает, что одно значение будет чётным, а другое нечётное.



Ответ:
185100918194




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


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

(№ 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 значение минимальное из всех возможных, значит, сумма останется максимальной.


Ответ:
1315940799380





28-03-2021 в 20:51:02







Похожая статья:

ЕГЭ по информатике 2021 - Задание 22 (Анализируем программу)

Здравствуйте! Будем тренироваться решать 22 задание из ЕГЭ по информат...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 1


Комментарии:

Было бы круто, если бы все задачи разбирались на python
Виталий 12-04-2021 в 14:07:24

Согласен в Виталием)
Menso 24-04-2021 в 15:23:47



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



Шифр Цезаря на C#
Алгоритм Евклида на C#





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy