Тренировка задания 27 ЕГЭ (27.1), вторая часть ЕГЭ. Тройки чисел

Крылов С.С., Чуркина Т.Е. «Типовые экзаменационные варианты», 2019, вариант 13 (20 вариантов):

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

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

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

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

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

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

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

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

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

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

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

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

2 3 2
2 3 3
2 2 1
3 3 5
1 1 1

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

5
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1

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

✍ Решение:
 

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

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

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

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

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

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

    В цикле перебираются все возможные суммы, и среди них ищется удовлетворяющая условию.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    var
      a: array[1..5, 1..3] of longint; 
      i1, i2, i3, i4, i5: longint; 
      s, sMin: longint;
     
    begin
      for i1 := 1 to 5 do 
        readln(a[i1, 1], a[i1, 2], a[i1, 3]); 
      sMin := 100000; 
      for i1 := 1 to 3 do 
        for i2 := 1 to 3 do 
          for i3 := 1 to 3 do
            for i4 := 1 to 3 do
              for i5 := 1 to 3 do 
              begin
                s := a[1, i1] + a[2, i2] + a[3, i3] + a[4, i4] + a[5, i5];
                if (s mod 2 = 0) and (s < sMin) then 
                  sMin := s
              end;
      if (sMin = 100000) then 
        sMin := 0; 
      writeln(sMin)
    end.

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

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

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

*
*


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