Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k = 109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих
Пример организации исходных данных во входном файле:
6
1 3 7
5 12 6
6 9 11
5 4 8
3 5 4
1 1 1
Для указанных входных данных, в случае, если k = 5, значением искомой суммы является
В ответе укажите два числа: сначала значение искомой суммы для
Ответ:
Будем последовательно считывать тройки чисел из файла и прибавлять
Приведём решение задачи на языке Pascal.
var
x, y, z: integer;
n: integer;
sum: int64;
minDif: integer;
f: text;
begin
assign(f,'C:\27_B.txt');
reset(f);
readln(f, n);
sum := 0;
minDif := 40001;
while not eof(f) do begin
readln(f, x, y, z);
if (x >= y) and (x >= z) then begin
sum := sum + x;
if (((abs(x - y)) mod 109 <> 0) and (abs(x - y) < minDif)) then
minDif := abs(x - y);
if (((abs(x - z)) mod 109 <> 0) and (abs(x - z) < minDif)) then
minDif := abs(x - z);
end
else if (y >= z) and (y >= x) then begin
sum := sum + y;
if (((abs(y - x)) mod 109 <> 0) and (abs(y - x) < minDif)) then
minDif := abs(y - x);
if (((abs(y - z)) mod 109 <> 0) and (abs(y - z) < minDif)) then
minDif := abs(y - z);
end
else if (z >= x) and (z >= y) then begin
sum := sum + z;
if (((abs(z - y)) mod 109 <> 0) and (abs(z - y) < minDif)) then
minDif := abs(z - y);
if (((abs(z - x)) mod 109 <> 0) and (abs(z - x) < minDif)) then
minDif := abs(z - x);
end;
end;
if sum mod 109 <> 0 then
writeln(sum)
else writeln(sum - minDif);
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Дмитрия Крылова на языке Python:
f = open('27a.txt')
n = int(f.readline())
summ = 0
nekr109 = 10000000000000
for i in range(n):
a,b,c = f.readline().split()
a = int(a)
b = int(b)
c = int(c)
summ += max(a, b, c)
n1 = max(a, b, c) - min(a, b, c)
sr = a+b+c-max(a, b, c) - min(a, b, c)
n2 = max(a, b, c) - sr
if n1%109!=0:
nekr109 = min(nekr109, n1)
if n2%109!=0:
nekr109 = min(nekr109, n2)
if summ%109!=0:
print(summ)
else:
print(summ-nekr109)
Приведём решение Юрия Красильникова на языке Python:
a = [sorted(map(int,s.split())) for s in open('27.txt')][1:]
s = sum(x[2] for x in a)
difs = [x[2]-x[0] for x in a if (x[2]-x[0])%109 !=0 ] + [x[2]-x[1] for x in a if (x[2]-x[1])%109 !=0 ]
print(s if s%109 != 0 else s-min(difs))