В текстовом файле записан набор пар натуральных чисел, не превышающих 10 000. Необходимо выбрать из набора некоторые пары так, чтобы второе число в каждой выбранной паре было нечётным, сумма бо́льших чисел во всех выбранных парах была чётной, а сумма меньших — нечётной. Какую наибольшую сумму чисел во всех выбранных парах можно при этом получить?
Входные данные.
Первая строка входного файла содержит целое
Пример входного файла:
4
5 3
7 15
7 14
12 9 В данном случае есть три подходящие пары: (5, 3), (7, 15) и (12, 9). Пара (7, 14) не подходит, так как в ней второе число чётное. Чтобы удовлетворить требования, надо взять пары (5, 3), (7, 15) и (12, 9). Сумма бо́льших чисел в этом случае
Вам даны два входных файла
Ответ:
Приведём решение на языке 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 y % 2 == 1:
if x > y:
sum1 = sum1 + y
sum0 = sum0 + x
if (y % 2 == 1) and (x % 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
else:
sum1 = sum1 + x
sum0 = sum0 + y
if (y % 2 == 1) and (x % 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
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('27.txt')
sum0 = sum1 = 0
m = [0] + 3*[20001]
for i in range(int(f.readline())):
x, y = map(int, f.readline().split())
if y % 2 == 0: continue
if x > y: x,y = y,x
sum0 += x
sum1 += y
j = 2*(y%2) + x%2
m[j] = min(m[j], x+y)
i = (2*(sum1%2) + sum0%2) ^ 1
print(sum0 + sum1 - min(m[i], sum(m) - m[i]))
Приведём решение задачи на языке Pascal.
Будем последовательно считывать пары из файла. Для каждой считываемой пары будем проверять чётность второго числа в паре. Если второе число в паре чётное — эта пара не рассматривается. Большее число в считанной паре будем записывать
1) оба числа в паре нечётные —
2) большее число в паре нечётное, меньшее число в паре чётное —
3) большее число в паре чётное, меньшее число в паре нечётное —
Перед тем, как выводить найденную сумму, будем делать проверку переменных
Если значение
Если значение
Если значение
Если значение
Приведём решение задачи на языке 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 y mod 2 = 1 then begin
if x > y then begin
sum1 := sum1 + y;
sum0 := sum0 + x;
if (y mod 2 = 1) and (x 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
else begin
sum1 := sum1 + x;
sum0 := sum0 + y;
if (y mod 2 = 1) and (x 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;
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.