Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 20.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
Решение. Последовательно считывая данные из файла, будем прибавлять к сумме минимальное число в паре. Также заметим, что в случае, если получившееся в результате суммирование минимальных чисел во всех парах число будет кратно трём, достаточно будет прибавить к этой сумме минимальную разницу между какими-либо двумя числами. Для этого при считывании пар помимо минимального числа в каждой паре будем искать минимальную разницу среди пар, не кратную трём.
Приведём решение задачи на языке Pascal.
var
x, y: integer;
n: integer;
sum: integer;
mindif: integer;
f: text;
begin
assign(f,'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 ответ — 67088, из файла B — 200157478.
Приведём решение Романа Князева на языке Python.
f = open('27-A_demo.txt')
n = int(f.readline())
s = 0
minn = 20001
d = 0
for i in range(n):
x, y = map(int, f.readline().split())
s += min(x, y)
d = abs(x-y)
if d % 3 != 0:
minn = min(d, minn)
if s % 3 !=0:
print(s)
else:
print(s+minn)
f.close()
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Артёма Гридина на языке Python.
PDF-версии: 