В текстовом файле записан набор пар натуральных чисел, не превышающих 10 000. Необходимо выбрать из набора некоторые пары так, чтобы первое число в каждой выбранной паре было нечётным, сумма бо́льших чисел во всех выбранных парах была нечётной, а сумма меньших — чётной. Какую наибольшую сумму чисел во всех выбранных парах можно при этом получить?
Входные данные.
Первая строка входного файла содержит целое число N — общее количество пар в наборе. Каждая из следующих N строк содержит пару чисел.
Пример входного файла:
4
5 2
8 15
7 14
11 9 В данном случае есть три подходящие пары: (5, 2), (7, 14) и (11, 9). Пара (8, 15) не подходит, так как в ней первое число чётное. Чтобы удовлетворить требования, надо взять пары (7, 14) и (11, 9). Сумма бо́льших чисел в этом случае
Вам даны два входных файла
Ответ:
Будем последовательно считывать пары из файла. Для каждой считываемой пары будем проверять чётность первого числа в паре. Если первое число в паре чётное — эта пара не рассматривается. Большее число в считанной паре будем записывать
1) оба числа в паре нечётные —
2) большее число в паре чётное, меньшее число в паре нечётное —
3) большее число в паре нечётное, меньшее число в паре чётное —
Перед тем, как выводить найденную сумму, будем делать проверку переменных sum0 и sum1 на чётность.
Если значение
Если значение в переменной sum0 нечётно, а значение в переменной sum1 чётно, тогда сравниваем значения
Если значение в переменной sum0 нечётно и значение
Если значение в переменной sum0 чётно и значение в переменной sum1 чётно, тогда сравниваем значения
Приведём решение задачи на языке Pascal.
var
i, n, x, y, min1, min2, min3: integer;
sum0, sum1: int64;
f: text;
begin
assign(f,'C:\inf_26_04_21_27b.txt');
reset(f);
readln(f, n);
sum0 := 0;
sum1 := 0;
min1 := 20001;
min2 := 20001;
min3 := 20001;
for i := 1 to n do begin
readln(f, x, y);
if x mod 2 = 1 then begin
if x > y then begin
sum1 := sum1 + x;
sum0 := sum0 + y;
if (x mod 2 = 1) and (y mod 2 = 1) and ((x + y) < min1) then
min1 := x + y;
if (x mod 2 = 0) and (y mod 2 = 1) and ((x + y) < min2) then
min2 := x + y;
if (x mod 2 = 1) and (y mod 2 = 0) and ((x + y) < min3) then
min3 := x + y;
end
else begin
sum1 := sum1 + y;
sum0 := sum0 + x;
if (x mod 2 = 1) and (y mod 2 = 1) and ((x + y) < min1) then
min1 := x + y;
if (y mod 2 = 0) and (x mod 2 = 1) and ((x + y) < min2) then
min2 := x + y;
if (y mod 2 = 1) and (x mod 2 = 0) and ((x + y) < min3) then
min3 := x + y;
end;
end;
end;
if (sum0 mod 2 = 0) and (sum1 mod 2 = 1) then
writeln(sum0 + sum1)
else if (sum0 mod 2 = 1) and (sum1 mod 2 = 0) then
if min1 < min2 + min3 then
writeln(sum0 + sum1 - min1)
else writeln(sum0 + sum1 - min2 - min3)
else if (sum0 mod 2 = 1) and (sum1 mod 2 = 1) then
if min2 < min3 + min1 then
writeln(sum0 + sum1 - min2)
else writeln(sum0 + sum1 - min3 - min1)
else if (sum0 mod 2 = 0) and (sum1 mod 2 = 0) then
if min3 < min2 + min1 then
writeln(sum0 + sum1 - min3)
else writeln(sum0 + sum1 - min2 - min1);
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("inf_26_04_21_27b.txt")
n = int(f.readline())
sum0 = 0
sum1 = 0
min1 = 20001
min2 = 20001
min3 = 20001
for i in f:
x, y = i.split()
x = int(x)
y = int(y)
if x % 2 == 1:
if x > y:
sum1 = sum1 + x
sum0 = sum0 + y
if (x % 2 == 1) and (y % 2 == 1) and ((x + y) < min1):
min1 = x + y
if (x % 2 == 0) and (y % 2 == 1) and ((x + y) < min2):
min2 = x + y
if (x % 2 == 1) and (y % 2 == 0) and ((x + y) < min3):
min3 = x + y
else:
sum1 = sum1 + y
sum0 = sum0 + x
if (x % 2 == 1) and (y % 2 == 1) and ((x + y) < min1):
min1 = x + y
if (y % 2 == 0) and (x % 2 == 1) and ((x + y) < min2):
min2 = x + y
if (y % 2 == 1) and (x % 2 == 0) and ((x + y) < min3):
min3 = x + y
if (sum0 % 2 == 0) and (sum1 % 2 == 1):
print(sum0 + sum1)
elif (sum0 % 2 == 1) and (sum1 % 2 == 0):
if min1 < min2 + min3:
print(sum0 + sum1 - min1)
else:
print(sum0 + sum1 - min2 - min3)
elif (sum0 % 2 == 1) and (sum1 % 2 == 1):
if min2 < min3 + min1:
print(sum0 + sum1 - min2)
else:
print(sum0 + sum1 - min3 - min1)
elif (sum0 % 2 == 0) and (sum1 % 2 == 0):
if min3 < min2 + min1:
print(sum0 + sum1 - min3)
else:
print(sum0 + sum1 - min2 - min1)
Приведём решение Матвея Курченко на языке Python.
f = open('inf_26_04_21_27b.txt')
n = int(f.readline())
s1 = s2 = 0
mn1 = mn2 = mn3 = mn4 = 1e9
for i in range(n):
a, b = map(int, f.readline().split())
if a%2 == 1:
s1 += max(a, b)
s2 += min(a, b)
r = max(a, b)
h = min(a, b)
if r%2 == 0 and h%2 == 1:
mn1 = min(mn1, r+h)
if r%2 == 1 and h%2 == 1:
mn2 = min(mn2, r+h)
if r%2 == 1 and h%2 == 0:
mn3 = min(mn3, r+h)
if s1%2 == 1 and s2%2 == 0:
print(s1 + s2)
if s1%2 == 0 and s2%2 == 0:
print(s1 + s2 - min(mn3, mn1 + mn2))
if s1%2 == 0 and s2%2 == 1:
print(s1 + s2 - mn2)
if s1%2 == 1 and s2%2 == 1:
print(s1 + s2 - min(mn1, mn2+mn3))
Приведём решение Юрия Лысакова на языке Python.
f = open('inf_26_04_21_27b.txt')
n = int(f.readline())
a = []
for i in f:
s = i.split()
s = list(map(int,s))
if s[0] % 2 == 1:
m2 = max(s[0],s[1])
m1 = min(s[0],s[1])
a.append([m1+m2,m2,m1])
a.sort()
g,z1,z2 = 0,0,0
g = sum(i[0] for i in a)
z1 = sum(i[2] for i in a)
z2 = sum(i[1] for i in a)
if (z2 % 2 == 1) and (z1 % 2 == 0):
print(g)
else:
for i in a:
if ((z2 - i[1]) % 2 == 1) and ((z1 - i[2]) % 2 == 0):
mm = g - i[1] - i[2]
x = a.index(i)
break
for k1 in range(0,x-1):
for k2 in range(k1+1,x):
if ((z2 - a[k1][1] - a[k2][1]) % 2 == 1) and ((z1 - a[k1][2] - a[k2][2]) % 2 == 0):
mm1 = g - a[k1][1] - a[k2][1] - a[k1][2] - a[k2][2]
mm = max(mm,mm1)
print(mm)