Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 784594 8819088760
Условие
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k = 109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Файл A
Файл B
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 20 000.
Пример организации исходных данных во входном файле:
6
1 3 7
5 12 6
6 9 11
5 4 8
3 5 4
1 1 1
Для указанных входных данных, в случае, если k = 5, значением искомой суммы является число 44.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Подсказки — как подойти к решению
- Для каждой тройки бери максимальное число — сумма получится самой большой. Если она делится на делитель из условия, её придётся уменьшить, заменив одно из выбранных чисел.
- Уменьшать нужно на минимальную разницу между числами тройки, но только на такую, которая сама не делится на делитель: иначе остаток суммы не изменится. Суммы для файлов A и B считай отдельно.
Решение
Будем последовательно считывать тройки чисел из файла и прибавлять к переменной sum максимальное число в тройке. Также будем находить минимальную разницу между максимальным числом в тройке и минимальным числом в тройке, между максимальным числом в тройке и средним по значению числом в тройке. Разница между числами при этом не должна делиться на 109 без остатка. В конце выполнения программы будем проверять, делится ли найденная сумма на 109 без остатка, и если не делится — будем выводить найденную сумму, иначе будем выводить найденную сумму, вычтя из неё найденную минимальную разницу между числами.
Приведём решение задачи на языке Pascal.
var
x, y, z: integer;
n: integer;
sum: int64;
minDif: integer;
f: text;
begin
assign(f,'C:\27_B.txt');
reset(f);
readln(f, n);
sum := 0;
minDif := 40001;
while not eof(f) do begin
readln(f, x, y, z);
if (x >= y) and (x >= z) then begin
sum := sum + x;
if (((abs(x - y)) mod 109 <> 0) and (abs(x - y) < minDif)) then
minDif := abs(x - y);
if (((abs(x - z)) mod 109 <> 0) and (abs(x - z) < minDif)) then
minDif := abs(x - z);
end
else if (y >= z) and (y >= x) then begin
sum := sum + y;
if (((abs(y - x)) mod 109 <> 0) and (abs(y - x) < minDif)) then
minDif := abs(y - x);
if (((abs(y - z)) mod 109 <> 0) and (abs(y - z) < minDif)) then
minDif := abs(y - z);
end
else if (z >= x) and (z >= y) then begin
sum := sum + z;
if (((abs(z - y)) mod 109 <> 0) and (abs(z - y) < minDif)) then
minDif := abs(z - y);
if (((abs(z - x)) mod 109 <> 0) and (abs(z - x) < minDif)) then
minDif := abs(z - x);
end;
end;
if sum mod 109 <> 0 then
writeln(sum)
else writeln(sum - minDif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 784594, из файла B — 8819088760.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Дмитрия Крылова на языке Python:
f = open('27a.txt')
n = int(f.readline())
summ = 0
nekr109 = 10000000000000
for i in range(n):
a,b,c = f.readline().split()
a = int(a)
b = int(b)
c = int(c)
summ += max(a, b, c)
n1 = max(a, b, c) - min(a, b, c)
sr = a+b+c-max(a, b, c) - min(a, b, c)
n2 = max(a, b, c) - sr
if n1%109!=0:
nekr109 = min(nekr109, n1)
if n2%109!=0:
nekr109 = min(nekr109, n2)
if summ%109!=0:
print(summ)
else:
print(summ-nekr109)
Приведём решение Юрия Красильникова на языке Python:
a = [sorted(map(int,s.split())) for s in open('27.txt')][1:]
s = sum(x[2] for x in a)
difs = [x[2]-x[0] for x in a if (x[2]-x[0])%109 !=0 ] + [x[2]-x[1] for x in a if (x[2]-x[1])%109 !=0 ]
print(s if s%109 != 0 else s-min(difs))
Типичные ошибки
- Вычтена разница, кратная делителю, поэтому остаток суммы остался нулевым и ответ не подходит под условие. Бери разницу, которая на делитель не делится.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике