Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 541 300229428
Условие
Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите максимально возможную сумму всех чисел в третьей группе.
Входные данные.
Файл A
Файл B
Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
3
1 2 3
5 12 4
6 9 7
Для указанных данных искомая сумма равна 24, она соответствует такому распределению чисел по группам: (1, 5, 6), (2, 4, 7), (3, 12, 9).
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Подсказки — как подойти к решению
- В каждой тройке числа раздаются по трём группам, поэтому в группу с максимальной суммой логично отправлять самое большое число тройки, а два других — в оставшиеся группы.
- Чётность двух групп нужно выдержать одновременно: если после раздачи чётности не те, поменяй местами два числа из разных групп, потеряв как можно меньше. В ответе два числа — для A и B.
Решение
Последовательно считывая данные из файла, будем прибавлять к первой сумме (переменная sumAns) максимальное число в тройке, к третьей сумме (переменная sum3) минимальное число в тройке, а ко второй сумме (переменная sum2) оставшееся число в тройке. Также в переменную minDif будем записывать значение минимальной нечётной разницы между между числами, накапливаемыми в первой сумме, и одним из чисел, накапливаемых в других суммах. Таким образом, если в переменных sum2 и sum3 по окончании работы программы одновременно будут два нечётных числа или два чётных числа, будем отнимать от искомой суммы значение переменной minDif.
Приведём решение задачи на языке Pascal.
var
x, y, z: integer;
n: integer;
sumAns, sum2, sum3: integer;
minDif: integer;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
sumAns := 0;
sum2 := 0;
sum3 := 0;
minDif := 20001;
while not eof(f) do begin
readln(f, x, y, z);
if (x >= y) and (x >= z) then begin
sumAns := sumAns + x;
if (y >= z) then begin
sum2 := sum2 + y;
sum3 := sum3 + z;
end
else begin
sum3 := sum3 + y;
sum2 := sum2 + z;
end;
if (((abs(x - y)) mod 2 <> 0) and (abs(x - y) < minDif)) then
minDif := abs(x - y)
else if (((abs(x - z)) mod 2 <> 0) and (abs(x - z) < minDif)) then
minDif := abs(x - z);
end
else if (y >= z) and (y >= x) then begin
sumAns := sumAns + y;
if (x >= z) then begin
sum2 := sum2 + x;
sum3 := sum3 + z;
end
else begin
sum3 := sum3 + x;
sum2 := sum2 + z;
end;
if (((abs(y - x)) mod 2 <> 0) and (abs(y - x) < minDif)) then
minDif := abs(y - x)
else if (((abs(y - z)) mod 2 <> 0) and (abs(y - z) < minDif)) then
minDif := abs(y - z);
end
else if (z >= x) and (z >= y) then begin
sumAns := sumAns + z;
if (x >= y) then begin
sum2 := sum2 + x;
sum3 := sum3 + y;
end
else begin
sum3 := sum3 + x;
sum2 := sum2 + y;
end;
if (((abs(z - x)) mod 2 <> 0) and (abs(z - x) < minDif)) then
minDif := abs(z - x)
else if (((abs(z - y)) mod 2 <> 0) and (abs(z - y) < minDif)) then
minDif := abs(z - y);
end;
end;
if (sum2 + sum3) mod 2 <> 0 then
writeln(sumAns)
else writeln(sumAns - minDif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 541, из файла B — 300229428.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("27-B.txt")
s = f.readlines()
n = int(s[0])
sumAns = 0
sum2 = 0
sum3 = 0
minDif = 20001
for i in range(1, n + 1):
x, y, z = map(int, s[i].split())
if (x >= y) and (x >= z):
sumAns = sumAns + x
if y >= z:
sum2 = sum2 + y
sum3 = sum3 + z
else:
sum3 = sum3 + y
sum2 = sum2 + z
if ((abs(x - y)) % 2 != 0) and (abs(x - y) < minDif): minDif = abs(x - y)
elif ((abs(x - z)) % 2 != 0) and (abs(x - z) < minDif): minDif = abs(x - z)
elif (y >= z) and (y >= x):
sumAns = sumAns + y
if x >= z:
sum2 = sum2 + x
sum3 = sum3 + z
else:
sum3 = sum3 + x
sum2 = sum2 + z
if ((abs(y - x)) % 2 != 0) and (abs(y - x) < minDif): minDif = abs(y - x)
elif ((abs(y - z)) % 2 != 0) and (abs(y - z) < minDif): minDif = abs(y - z)
elif (z >= x) and (z >= y):
sumAns = sumAns + z
if x >= y:
sum2 = sum2 + x
sum3 = sum3 + y
else:
sum3 = sum3 + x
sum2 = sum2 + y
if ((abs(z - x)) % 2 != 0) and (abs(z - x) < minDif):
minDif = abs(z - x)
elif ((abs(z - y)) % 2 != 0) and (abs(z - y) < minDif):
minDif = abs(z - y)
if (sum2 + sum3) % 2 != 0: print(sumAns)
else: print(sumAns - minDif)
Приведём другое решение Фертик Маргариты на языке Python.
f = open('27.txt')
n = int(f.readline())
sum_a = sum_b = sum_max = 0
min_razn = 100000000
for i in range(n):
a, b, c = map(int, f.readline().split())
sum_max += max(a, b, c)
sum_a += min(a, b, c)
average = a + b + c - max(a, b, c) - min(a, b, c)
sum_b += average
if max(a, b, c) - average < min_razn and max(a, b, c) - average != 0 and max(a, b, c) - average % 2 != 0 and max(a, b, c) - min(a,b,c) % 2 != 0:
min_razn = max(a, b, c) - average
if (sum_b % 2) == (sum_a % 2): print(sum_max - min_razn)
else: print(sum_max)
Приведём решение Юрия Лысакова на языке Python.
f = open('27.txt')
n = int(f.readline())
a = []
d,k,p = 0,0,0
for i in f:
s = i.split()
s = list(map(int,s))
s.sort(reverse=True)
d = min((s[0] - s[1]),(s[0] - s[2]))
a.append(d)
k += s[1] + s[2]
p += s[0]
a.sort()
g = 0
while k % 2 == 0:
if (k + a[g]) % 2 == 1:
p -= a[g]
break
else:
g += 1
print(p)
Приведём другое решение на языке Python.
n = [sorted(list(map(int, a.split(' ')))) for a in open('27.txt').readlines()[1:]] # массив отсортированных чисел в тройках
sum_min = sum([a[0] for a in n])
sum_aver = sum([a[1] for a in n])
sum_max = sum([a[2] for a in n])
if sum_min%2 == sum_aver%2:
sum_max += max([a[1] - a[2] for a in n if a[1]%2 != a[2]%2] + [a[0] - a[2] for a in n if a[1]%2 != a[2]%2]) # максимальная выгода, которую можно получить после перестановки чисел
print(sum_max)
Типичные ошибки
- Чётность одной из групп не совпала с условием: проверяй обе группы, а не только сумму третьей. Распределение должно оставаться допустимым по чётности.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике