Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась
Входные данные.
Первая строка входного файла содержит
Пример организации исходных данных во входном файле:
6
1 3
5 10
6 9
5 4
3 3
1 1
Для указанных данных искомая сумма
В ответе укажите два числа: сначала значение искомой суммы для
Предупреждение: для обработки
Ответ:
Последовательно считывая данные из файла, будем прибавлять к сумме максимальное число в паре. Если сумма чисел делится
Приведём решение задачи на языке Pascal.
var
x, y: integer;
n: integer;
sum: integer;
dif1, dif2, dif3, dif4: integer;
f: text;
begin
assign(f,'C:\27.txt');
reset(f);
readln(f, n);
sum := 0;
dif1 := 20001;
dif2 := 20001;
dif3 := 20001;
dif4 := 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) mod 3 = 1) and (abs(x-y) < dif1) then begin
dif2 := dif1;
dif1 := abs(x-y);
end
else if (abs(x-y) mod 3 = 1) and (abs(x-y) < dif2) then
dif2 := abs(x-y)
else if (abs(x-y) mod 3 = 2) and (abs(x-y) < dif3) then begin
dif4 := dif3;
dif3 := abs(x-y);
end
else if (abs(x-y) mod 3 = 2) and (abs(x-y) < dif4) then
dif4 := abs(x-y);
end;
if sum mod 3 = 0 then
writeln(sum)
else if (sum mod 3 = 1) then
if ((sum - dif1) > (sum - dif3 - dif4)) then
writeln(sum - dif1)
else
writeln(sum - dif3 - dif4)
else if (sum mod 3 = 2) then
if ((sum - dif3) > (sum - dif1 - dif2)) then
writeln(sum - dif3)
else
writeln(sum - dif1 - dif2)
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Петра Полякова на языке Python.
f = open('27_B.txt')
n = int(f.readline())
summ = 0
raznica3 = []
for i in range(n):
a, b = f.readline().split()
a = int(a)
b = int(b)
summ = summ + max(a, b)
r1 = max(a, b) - min(a, b)
if r1 % 3 != 0:
raznica3.append(r1)
raznica3 = sorted(raznica3)
if summ % 3 == 0:
print(summ)
else:
i = 0
k = 0
while summ % 3 != 0:
i = i + 1
if summ % 3 != 0:
summ = summ - raznica3[i]
if summ % 3 == 0:
print(summ)
break
else:
summ = summ + raznica3[i]
i = i + 1
if k < 1:
summ = summ - raznica3[0] - raznica3[1]
if summ % 3 == 0:
print(summ)
k = k + 1
break
else:
summ = summ + raznica3[0] + raznica3[1]
k = k + 1
Приведём решение Юрия Лысакова на языке Python.
f = open('inf_22_10_20_27b.txt')
f.readline()
a1,a2 = [],[]
s = 0
for i in f:
b = i.split()
c = [int(b[0]),int(b[1])]
c.sort()
s += c[1]
if (c[1] - c[0]) % 3 == 1: a1.append(c[1] - c[0])
if (c[1] - c[0]) % 3 == 2: a2.append(c[1] - c[0])
a1.sort()
a2.sort()
if s % 3 == 0: print(s)
else:
if s % 3 == 1:
s1 = s - min(a1[0],a2[0]+a2[1])
if s % 3 == 2:
s1 = s - min(a2[0],a1[0]+a1[1])
print(s1)
Приведём решение Юрия Красильникова на языке Python.
a = [list(map(int,s.split())) for s in open('inf_22_10_20_27b.txt')][1:]
s = sum([max(x) for x in a])
difs = [[],[],[]]
for x in a:
d = abs(x[1]-x[0])
difs[d%3].append(d)
for i in range(1,3): difs[i].sort()
m = []
s3 = s%3
if s3 != 0:
if difs[s3]: m.append(difs[s3][0])
if len(difs[3-s3]) >= 2: m.append(sum(difs[3-s3][:2]))
print(s-min(m))
else:
print(s)