Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 127127 399762080
Условие
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Файл A
Файл B
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Подсказки — как подойти к решению
- Файл нужно обработать программой, причём для второго файла перебор всех вариантов не успеет выполниться. Ищи однопроходный алгоритм, который помнит несколько чисел, а не всю последовательность.
- В каждой паре выгодно брать большее число — это даёт верхнюю границу суммы. Но условие ограничивает делимость суммы, поэтому по ходу чтения важно запоминать не только максимумы, но и кое-что о разнице чисел внутри пары.
- Подумай, что делать, если набранная сумма всё-таки делится на делитель: какую пару выгоднее всего «подправить» и какую величину нужно было запоминать при чтении, чтобы эта правка оказалась минимальной.
Решение
Последовательно считывая данные из файла, будем прибавлять к сумме максимальное число в паре. Также заметим, что в случае, если получившееся в результате суммирования максимальных чисел во всех парах число будет кратно трём, достаточно будет вычесть из этой суммы минимальную разницу между какими-либо двумя числами. Для этого при считывании пар помимо максимального числа в каждой паре будем искать минимальную разницу среди пар, не кратную трём.
Приведём решение задачи на языке Pascal.
var
x, y: longint;
n: longint;
sum: longint;
mindif: longint;
f: text;
begin
assign(f,'C:\27-A.txt');
reset(f);
readln(f, n);
sum := 0;
mindif := 20001;
while not eof(f) do begin
readln(f, x, y);
if x > y then
sum := sum + x
else
sum := sum + y;
if (abs(x - y) < mindif) and (abs(x-y) mod 3 <> 0) then mindif := abs(x-y);
end;
if sum mod 3 <> 0 then
writeln(sum)
else
writeln(sum - mindif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 127127, из файла B — 399762080.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open("27-B_demo (2).txt") # для файла A замените название
s = f.readlines()
n = int(s[0]) # количество пар
summi = 0
d = 10**6
for i in range(1, n + 1):
x, y = map(int, s[i].split())
summi += max(x, y)
if abs(x - y) % 3 != 0:
d = min(d, abs(x - y))
if summi % 3 != 0:
print(summi)
else:
print(summi - d)
Приведём решение Юрия Красильникова на языке Python:
a=[list(map(int,s.split())) for s in open('27-B_demo.txt')][1:]
s=sum([max(x) for x in a])
d=min([abs(x[0]-x[1]) for x in a if (x[0]-x[1])%3!=0])
print(s if s%3!=0 else s-d)
Типичные ошибки
- Значения записаны в обратном порядке: сначала в ответе идёт результат для файла A, затем для файла B. Проверь, какой файл обрабатывается первым.
- Оба значения совпали, потому что при втором запуске не было заменено имя файла и программа дважды прочитала одни и те же данные. Убедись, что для каждого файла указан свой путь.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике