Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 121184 36898658
Условие
Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы чётность суммы выбранных чисел совпадала с чётностью большинства выбранных чисел и при этом сумма выбранных чисел была как можно больше. Определите максимальную сумму, которую можно получить при таком выборе. Гарантируется, что удовлетворяющий условиям выбор возможен.
Входные данные.
Файл A
Файл B
Первая строка входного файла содержит число N — общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
5
15 8
5 11
6 3
7 2
9 14
Для указанных данных надо выбрать числа 15, 11, 6, 7 и 14. Большинство из них нечётны, сумма выбранных чисел равна 53 и тоже нечётна. В ответе надо записать число 53.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Подсказки — как подойти к решению
- Набор состоит из нечётного числа пар, поэтому большинство выбранных чисел всегда определено. Сначала выбери в каждой паре большее число и посчитай, сколько из выбранных чётны.
- Затем сверь чётность суммы с чётностью большинства. Если не совпало, замени одно или два выбранных числа с минимальной потерей — заранее найди самые маленькие разницы внутри пар.
Решение
Последовательно считывая данные из файла, будем прибавлять к сумме значение максимального числа в паре, при этом, если число чётное, будем увеличивать значение переменной 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)
Типичные ошибки
- Чётность суммы не совпала с чётностью большинства выбранных чисел: условие двойное. Пересчитай, каких чисел в выборе больше, и только потом итоговую сумму.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике