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