СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Сайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 27424

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

Входные данные.

Файл A

Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

6

1 3

5 12

6 9

5 4

3 3

1 1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

 

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

 

Ответ:

Решение.

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

 

Приведём решение задачи на языке Pascal.

var

x, y: integer;

n: integer;

sum: integer;

mindif: integer;

f: text;

begin

assign(f,'C:\27-A.txt');

reset(f);

readln(f, n);

sum := 0;

mindif := 20001;

while not eof(f) do begin

readln(f, x, y);

if x > y then

sum := sum + x

else

sum := sum + y;

if (abs(x - y) < mindif) and (abs(x-y) mod 3 <> 0) then mindif := abs(x-y);

end;

if sum mod 3 <> 0 then

writeln(sum)

else

writeln(sum - mindif);

end.

В результате работы данного алгоритма при вводе данных из файла A ответ — 127127, из файла B — 399762080.

 

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Источник: Демонстрационная версия ЕГЭ—2021 по информатике.