Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите максимально возможную сумму всех чисел в третьей группе.
Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
3
1 2 3
5 12 4
6 9 7
Для указанных данных искомая сумма равна 24, она соответствует такому распределению чисел по группам: (1, 5, 6), (2, 4, 7), (3, 12, 9).
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
Решение. Последовательно считывая данные из файла, будем прибавлять к первой сумме (переменная sumAns) максимальное число в тройке, к третьей сумме (переменная sum3) минимальное число в тройке, а ко второй сумме (переменная sum2) оставшееся число в тройке. Также в переменную minDif будем записывать значение минимальной нечётной разницы между между числами, накапливаемыми в первой сумме, и одним из чисел, накапливаемых в других суммах. Таким образом, если в переменных sum2 и sum3 по окончании работы программы одновременно будут два нечётных числа или два чётных числа, будем отнимать от искомой суммы значение переменной minDif.
Приведём решение задачи на языке Pascal.
var
x, y, z: integer;
n: integer;
sumAns, sum2, sum3: integer;
minDif: integer;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
sumAns := 0;
sum2 := 0;
sum3 := 0;
minDif := 20001;
while not eof(f) do begin
readln(f, x, y, z);
if (x >= y) and (x >= z) then begin
sumAns := sumAns + x;
if (y >= z) then begin
sum2 := sum2 + y;
sum3 := sum3 + z;
end
else begin
sum3 := sum3 + y;
sum2 := sum2 + z;
end;
if (((abs(x - y)) mod 2 <> 0) and (abs(x - y) < minDif)) then
minDif := abs(x - y)
else if (((abs(x - z)) mod 2 <> 0) and (abs(x - z) < minDif)) then
minDif := abs(x - z);
end
else if (y >= z) and (y >= x) then begin
sumAns := sumAns + y;
if (x >= z) then begin
sum2 := sum2 + x;
sum3 := sum3 + z;
end
else begin
sum3 := sum3 + x;
sum2 := sum2 + z;
end;
if (((abs(y - x)) mod 2 <> 0) and (abs(y - x) < minDif)) then
minDif := abs(y - x)
else if (((abs(y - z)) mod 2 <> 0) and (abs(y - z) < minDif)) then
minDif := abs(y - z);
end
else if (z >= x) and (z >= y) then begin
sumAns := sumAns + z;
if (x >= y) then begin
sum2 := sum2 + x;
sum3 := sum3 + y;
end
else begin
sum3 := sum3 + x;
sum2 := sum2 + y;
end;
if (((abs(z - x)) mod 2 <> 0) and (abs(z - x) < minDif)) then
minDif := abs(z - x)
else if (((abs(z - y)) mod 2 <> 0) and (abs(z - y) < minDif)) then
minDif := abs(z - y);
end;
end;
if (sum2 + sum3) mod 2 <> 0 then
writeln(sumAns)
else writeln(sumAns - minDif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 541, из файла B — 300229428.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("27-B.txt")
s = f.readlines()
n = int(s[0])
sumAns = 0
sum2 = 0
sum3 = 0
minDif = 20001
for i in range(1, n + 1):
x, y, z = map(int, s[i].split())
if (x >= y) and (x >= z):
sumAns = sumAns + x
if y >= z:
sum2 = sum2 + y
sum3 = sum3 + z
else:
sum3 = sum3 + y
sum2 = sum2 + z
if ((abs(x - y)) % 2 != 0) and (abs(x - y) < minDif): minDif = abs(x - y)
Приведём решение Юрия Лысакова на языке Python.
f = open('27.txt')
n = int(f.readline())
a = []
d,k,p = 0,0,0
for i in f:
s = i.split()
s = list(map(int,s))
s.sort(reverse=True)
d = min((s[0] - s[1]),(s[0] - s[2]))
a.append(d)
k += s[1] + s[2]
p += s[0]
a.sort()
g = 0
while k % 2 == 0:
if (k + a[g]) % 2 == 1:
p -= a[g]
break
else:
g += 1
print(p)
Приведём другое решение на языке Python.
n = [sorted(list(map(int, a.split(' ')))) for a in open('27.txt').readlines()[1:]] # массив отсортированных чисел в тройках
sum_min = sum([a[0] for a in n])
sum_aver = sum([a[1] for a in n])
sum_max = sum([a[2] for a in n])
if sum_min%2 == sum_aver%2:
sum_max += max([a[1] - a[2] for a in n if a[1]%2 != a[2]%2] + [a[0] - a[2] for a in n if a[1]%2 != a[2]%2]) # максимальная выгода, которую можно получить после перестановки чисел
PDF-версии: 