27 задание ЕГЭ информатика, связанное с вводом троек положительных целых

27_1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

✍ Решение:

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

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

Пример правильной и эффективной программы для задания Б на языке Паскаль (версия 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 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):

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

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.

К оглавлению