Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы чётность суммы выбранных чисел совпадала с чётностью большинства выбранных чисел и при этом сумма выбранных чисел была как можно больше. Определите максимальную сумму, которую можно получить при таком выборе. Гарантируется, что удовлетворяющий условиям выбор возможен.
Входные данные.
Первая строка входного файла содержит
Пример входного файла:
5
15 8
5 11
6 3
7 2
9 14
Для указанных данных надо выбрать числа 15, 11, 6, 7 и 14. Большинство из них нечётны, сумма выбранных чисел
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для
Предупреждение: для обработки
Ответ:
Последовательно считывая данные из файла, будем прибавлять к сумме значение максимального числа в паре, при этом, если число чётное, будем увеличивать значение
Приведём решение задачи на языке 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 (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
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 (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;
end;
if (count1 > count0) then begin
if sum mod 2 = 1 then
writeln(sum)
else if dif3 <= dif1 then
writeln(sum - dif3)
else if (count1 - count0) <> 1 then
writeln(sum - dif1)
else if (dif1 + dif2) < dif3 then
writeln(sum - dif1 - dif2)
else writeln(sum - dif3)
end
else begin
if sum mod 2 = 0 then
writeln(sum)
else if dif1 <= dif3 then
writeln(sum - dif1)
else if (count0 - count1) <> 1 then
writeln(sum - dif3)
else if (dif3 + dif4) < dif1 then
writeln(sum - dif3 - dif4)
else writeln(sum - dif1)
end;
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open("27-B (2).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 (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
else:
if y % 2 == 0: count0 = count0 + 1
else: count1 = count1 + 1
sum = sum + y
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
if count1 > count0:
if sum % 2 == 1:
print(sum)
elif dif3 <= dif1:
print(sum - dif3)
elif (count1 - count0) != 1:
print(sum - dif1)
elif (dif1 + dif2) < dif3:
print(sum - dif1 - dif2)
else: print(sum - dif3)
else:
if sum % 2 == 0:
print(sum)
elif dif1 <= dif3:
print(sum - dif1)
elif (count0 - count1) != 1:
print(sum - dif3)
elif (dif3 + dif4) < dif1:
print(sum - dif3 - dif4)
else: print(sum - dif1)
Приведём другое решение Селякова Дениса на языке Python.
f = open('27.txt')
s = f.readline()
n = int(s[0])
sum = 0
k0 = 0
k1 = 0
d1 = []
d0 = []
for i in range(1, 5556): # меняем в зависимости от s[0] в файле
x,y = map(int, f.readline().split())
sum += max(x, y)
if abs(x-y) % 2 == 1:
if max(x, y) % 2 == 1:
d1.append(abs(x-y))
else:
d0.append(abs(x-y))
if max(x,y) % 2 == 0:
k0 += 1
else:
k1 += 1
d1.sort()
d0.sort()
if ((k0>k1) and (sum % 2 == 0)) or ((k0 < k1) and (sum % 2 != 0)):
print(sum)
if k0 - k1 == 1 and sum % 2 != 0:
print(max(sum - d1[0], sum - d0[0]-d0[1]))
if k1 - k0 == 1 and sum % 2 == 0:
print(max(sum - d0[0], sum - d1[0]-d1[1]))
if k0 - k1 > 1 and sum % 2 != 0 or k1 - k0 > 1 and sum % 2 == 0:
print(max(sum - d0[0],sum - d1[0]))