Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы чётность суммы выбранных чисел совпадала с чётностью большинства выбранных чисел и при этом сумма выбранных чисел была как можно меньше. Определите минимальную сумму, которую можно получить при таком выборе. Гарантируется, что удовлетворяющий условиям выбор возможен.
Входные данные.
Первая строка входного файла содержит число N — общее количество пар в наборе. Каждая из следующих
Пример входного файла:
5
15 8
5 11
6 3
7 2
9 14
Для указанных данных надо выбрать числа 8, 5, 3, 2 и 9. Большинство из них нечётны, сумма выбранных чисел
Вам даны два входных файла
Предупреждение: для обработки
Ответ:
Последовательно считывая данные из файла, будем прибавлять к сумме значение минимального числа в паре, при этом, если число чётное, будем увеличивать значение
Приведём решение задачи на языке Pascal.
var
x, y, count0, count1: longint;
n: longint;
sum: longint;
dif1, dif2, dif3, dif4: longint;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
sum := 0;
dif1 := 20001;
dif2 := 20001;
dif3 := 20001;
dif4 := 20001;
count0 := 0;
count1 := 0;
while not eof(f) do begin
readln(f, x, y);
if x < y then begin
sum := sum + x;
if x mod 2 = 0 then count0 := count0 + 1
else count1 := count1 + 1;
if x mod 2 <> y mod 2 then begin
if (y - x < dif1) and (y mod 2 <> 0) then begin
dif2 := dif1;
dif1 := y - x;
end
else if (y - x < dif2) and (y mod 2 <> 0) then
dif2 := y - x;
if (y - x < dif3) and (y mod 2 = 0) then begin
dif4 := dif3;
dif3 := y - x;
end
else if (y - x < dif4) and (y mod 2 = 0) then
dif4 := y - x;
end;
end
else begin
if y mod 2 = 0 then count0 := count0 + 1
else count1 := count1 + 1;
sum := sum + y;
if x mod 2 <> y mod 2 then begin
if (x - y < dif1) and (x mod 2 <> 0) then begin
dif2 := dif1;
dif1 := x - y;
end
else if (x - y < dif2) and (x mod 2 <> 0) then
dif2 := x - y;
if (x - y < dif3) and (x mod 2 = 0) then begin
dif4 := dif3;
dif3 := x - y;
end
else if (x - y < dif4) and (x mod 2 = 0) then
dif4 := x - y;
end;
end;
end;
if (count1 > count0) then begin
if sum mod 2 = 1 then
writeln(sum)
else if dif1 <= dif3 then
writeln(sum + dif1)
else if (count1 - count0) <> 1 then
writeln(sum + dif3)
else if (dif3 + dif4) < dif1 then
writeln(sum + dif3 + dif4)
else writeln(sum + dif1)
end
else begin
if sum mod 2 = 0 then
writeln(sum)
else if dif3 <= dif1 then
writeln(sum + dif3)
else if (count0 - count1) <> 1 then
writeln(sum + dif1)
else if (dif1 + dif2) < dif3 then
writeln(sum + dif1 + dif2)
else writeln(sum + dif3)
end;
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("27-B (3).txt")
s = f.readlines()
n = int(s[0])
sum = 0
dif1 = 20001
dif2 = 20001
dif3 = 20001
dif4 = 20001
count0 = 0
count1 = 0
for i in range(1, n + 1):
x, y = map(int, s[i].split())
if x < y:
sum = sum + x
if x % 2 == 0: count0 = count0 + 1
else: count1 = count1 + 1
if x % 2 != y % 2:
if (y - x < dif1) and (y % 2 != 0):
dif2 = dif1
dif1 = y - x
elif (y - x < dif2) and (y % 2 != 0): dif2 = y - x
if (y - x < dif3) and (y % 2 == 0):
dif4 = dif3
dif3 = y - x
elif (y - x < dif4) and (y % 2 == 0):
dif4 = y - x
else:
if y % 2 == 0: count0 = count0 + 1
else: count1 = count1 + 1
sum = sum + y
if x % 2 != y % 2:
if (x - y < dif1) and (x % 2 != 0):
dif2 = dif1
dif1 = x - y
elif (x - y < dif2) and (x % 2 != 0):
dif2 = x - y
if (x - y < dif3) and (x % 2 == 0):
dif4 = dif3
dif3 = x - y
elif (x - y < dif4) and (x % 2 == 0):
dif4 = x - y
if count1 > count0:
if sum % 2 == 1:
print(sum)
elif dif1 <= dif3:
print(sum + dif1)
elif (count1 - count0) != 1:
print(sum + dif3)
elif (dif3 + dif4) < dif1:
print(sum + dif3 + dif4)
else: print(sum + dif1)
else:
if sum % 2 == 0:
print(sum)
elif dif3 <= dif1:
print(sum + dif3)
elif (count0 - count1) != 1:
print(sum + dif1)
elif (dif1 + dif2) < dif3:
print(sum + dif1 + dif2)
else: print(sum + dif3)