Решение. Последовательно считывая данные из файла, будем прибавлять к сумме значение максимального числа в паре, при этом, если число чётное, будем увеличивать значение переменной count0 на единицу, если нечётное — увеличивать значение переменной count1 на единицу. Поскольку может возникнуть ситуация, когда, например, получившаяся сумма будет чётной, а количество чётных чисел будет меньше количества нечётных чисел и будет отличаться от количества нечётных чисел на единицу, будем находить две минимальных разницы для ситуации, когда будет убираться два чётных числа (переменные dif3 и dif4), и две минимальных разницы для ситуации, когда будет убираться два нечётных числа (переменные dif1 и dif2).
Приведём решение задачи на языке 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.
В результате работы данного алгоритма при вводе данных из файла A ответ — 121184, из файла B — 36898658.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке 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]))
Приведём решение Юрия Красильникова на языке Python.
a = [sorted(list(map(int,s.split()))) for s in open('27-B.txt')][1:]
a.sort(key = lambda x: x[1]-x[0]) # сортировка по увеличению разности
m = 0 # сумма максимальных чисел в парах
c = [0]*2 # счётчик чётных и нечётных
difs = [[],[]] # нечётные разности для максимальных чётных и максимальных нечётных в парах
for x in a:
m += x[1]
c[x[1]%2] += 1
if (x[1]-x[0])%2 == 1: # только нечётные разности
difs[x[1]%2].append(x[1]-x[0])
if (m%2==0) != (c[0] > c[1]): # преобладающая чётность не совпадает с чётностью суммы
if abs(c[1]-c[0]) > 1: # меняем пару с наименьшей нечётной разностью
m -= min(difs[0][0],difs[1][0])
else: # либо одна пара с такой же чётностью, либо две с противоположной
m -= min(difs[m%2][0],sum(difs[1-m%2][:2]))
print(m)
