выбрать из каждой пары ровно одно число так, чтобы сумма
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
(для файла А) (для файла B)
Демонстрационный вариант ЕГЭ по информатике 2021 г. задания №27
Решение:
Чтобы получить максимально возможную сумму, будем брать из каждой пары самое большое число. Если полученная при этом сумма будет делиться на 3, её необходимо уменьшить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 3, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
f = open("27-B.txt") n = int(f.readline()) Dmin = 10001 s = 0 mx, mn = 0, 0 for i in range(n): a, b = map(int, f.readline().split()) mx=max(a, b) mn=min(a, b) s = s + mx if (mx - mn) % 3 > 0 and mx - mn < Dmin: Dmin = mx - mn if s % 3 == 0: s = s - Dmin print(s) |
Ответ:
127127
399762080