Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите минимально возможную сумму всех чисел в третьей группе.
Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
3
1 2 3
8 12 4
6 9 7
Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).
Вам даны два входных файла (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 - y)) mod 2 <> 0) and (abs(z - y) < minDif)) then
minDif := abs(z - y)
else if (((abs(z - x)) mod 2 <> 0) and (abs(z - x) < minDif)) then
minDif := abs(z - x);
end;
end;
if (sum2 + sum3) mod 2 <> 0 then
writeln(sumAns)
else writeln(sumAns + minDif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 185, из файла B — 100918194.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("27-B (1).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)
PDF-версии: 