Задание 27 ЕГЭ по информатике 2018. Вторая часть

Авторadmin / Опубликовано

Задание 27. Обработка строк или последовательности чисел. Сложность алгоритмов: Тренировочные варианты ЕГЭ по информатике

*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 27
 

Разбор 27 задания ЕГЭ по информатике 2018 года вариант 2 (Крылов С.С., Чуркина Т.Е. «Типовые тренировочные варианты», 10 вариантов):

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

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

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

Максимальная оценка за правильную программу — 2 балла.

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

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

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

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

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

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

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

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

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

1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

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

5
1 3 2
2 1 2
2 5 1
1 3 4
6 1 1

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

✍ Показать решение:

  
Задание Б

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

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

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 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.

Задание А

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