Розбір 27 завдання ЄДІ 2019 з інформатики з демоверсії

Максимальний бал для завдання А - 2
Максимальний бал для завдання Б - 4

Перевіряються елементи змісту:
- вміння створювати власні програми (30-50 рядків) для вирішення завдань середньої складності.

Елементи змісту, перевіряються на ЄДІ:
- основні етапи розробки програм. Розбиття задачі на підзадачі.

завдання 27

Вам пропонується два завдання зі схожими умовами: завдання А та завдання Б. Ви можете вирішувати обидва завдання або одне з них за своїм вибором. Завдання Б більш складне, його рішення оцінюється вище. Підсумкова оцінка виставляється як максимальна з оцінок за завдання А і Б.

Завдання А. Є набір даних, що складається з 6 пар позитивних цілих чисел. Необхідно вибрати з кожної пари рівно одне число так, щоб сума всіх обраних чисел не ділилася на 3 та при цьому була максимально можливою. Якщо отримати необхідну суму неможливо, як відповідь потрібно видати 0.
Напишіть програму для вирішення цього завдання. У цьому варіанті завдання оцінюється тільки правильність програми, час роботи і розмір використаної пам'яті не мають значення.
Максимальна оцінка за правильну програму-2 бали.

Завдання Б. Є набір даних, що складається з пар позитивних цілих чисел. Необхідно вибрати з кожної пари рівно одне число так, щоб сума всіх обраних чисел не ділилася на 3 та при цьому була максимально можливою. Якщо отримати необхідну суму неможливо, як відповідь потрібно видати 0.
Напишіть програму для вирішення цього завдання.
Постарайтеся зробити програму ефективної за часом і використовуваної пам'яті (або хоча б по одній з цих характеристик).
Програма вважається ефективною за часом, якщо час роботи програми пропорційно кількості пар чисел N. тобто при збільшенні N в k раз час роботи програми має збільшуватися не більше ніж в k раз.
Програма вважається ефективною по пам'яті, якщо розмір пам'яті, використаної в програмі для зберігання даних, не залежить від числа N і не перевищує 1 кілобайт.
Максимальна оцінка за правильну програму, ефективну за часом і пам'яті, - 4 бали.
Максимальна оцінка за правильну програму, ефективну за часом, але неефективну по пам'яті, - 3 бали.

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

НАГАДУЄМО! Не забудьте вказати, до якого завданням відноситься кожна з представлених Вами програм.

Перед текстом програми коротко опишіть Ваш алгоритм рішення, вкажіть використаний мову програмування і його версію (наприклад, Free Pascal 2.6.4).

Вхідні дані
Для варіанту А на вхід програмі подається шість рядків, кожна з яких містить два натуральних числа, що не перевищують 10 000.
Приклад вхідних даних для варіанту А:
1 3
5 12
6 9
5 4
3 3
1 + 1

Для варіанту Б на вхід програмі в першому рядку подається кількість пар N (1 ≤ N ≤100 000). Кожна з наступних N рядків містить два натуральних числа, що не перевищують 10 000.
Приклад вхідних даних для варіанту Б:
6
1 3
5 12
6 9
5 4
3 3
1 + 1

Приклад вихідних даних для наведених вище прикладів вхідних даних: 32

Завдання Б.
Cначала розглянемо рішення для більш загального завдання (варіант Б).

Щоб отримати максимально можливу суму, будемо брати з кожної пари найбільше число. Якщо отримана при цьому сума буде ділитися на 3, її необхідно зменшити. Для цього достатньо в одній з пар, де числа мають різні залишки при діленні на 3, замінити раніше вибране число на інше число з тієї ж пари. При цьому різниця між числами в парі повинна бути мінімально можливою. Якщо у всіх парах обидва числа мають однаковий залишок при діленні на 3, отримати потрібну суму неможливо.

Програма 1. Приклад правильної і ефективної програми для завдання Б на мові Паскаль.

Нижче наводиться приклад заснованої на цьому принципі програми мовою Паскаль.

Програма 2. Приклад правильної і ефективної програми для завдання Б на мові Паскаль

Завдання А.
Це завдання можна виконати «в лоб»: зберегти в масиві всі вихідні дані, перебрати всі можливі способи вибору одного елемента з кожної пари і знайти максимальну суму, відповідну умовам завдання.
Нижче наводиться приклад такого рішення

Приклад рішення задачі А на мові Паскаль.

var
a: array [1..6, 1..2] of longint;
i1, i2, i3, i4, i5, i6: longint;
s, sMax: longint;
begin
for i1: = 1 to 6 do readln (a [i1,1], a [i1,2]);
sMax: = 0;
for i1: = 1 to 2 do
for i2: = 1 to 2 do
for i3: = 1 to 2 do
for i4: = 1 to 2 do
for i5: = 1 to 2 do
for i6: = 1 to 2 do begin
s: = a [1, i1] + a [2, i2] + a [3, i3] + a [4, i4] + a [5, i5] + a [6, i6];
if (s mod 3 <> 0) and (s> sMax) then sMax: = s
end;
writeln (sMax)
end.