Динамика по остаткам
Когда из каждой пары нужно выбрать одно число так, чтобы сумма была наибольшей и не делилась на k, перебор вариантов невозможен. Задачу решает таблица лучших сумм для каждого остатка от деления на k, которую обновляют после каждой пары. Для условия «не делится» есть и короткий путь: взять большее число из каждой пары и при необходимости заменить выбор в одной паре с наименьшей подходящей разностью.
Наибольшая сумма с условием на остаток
Из каждой из пар выбирают одно число. Вариантов выбора , поэтому их не перебирают, а хранят только лучшую сумму для каждого остатка.
- Остаток суммы зависит только от остатков слагаемых: .
- Таблица:
best[r]— наибольшая сумма с остатком среди выборов из уже прочитанных пар. В началеbest = {0: 0}. - Новая пара: к каждой сумме таблицы прибавьте каждое число пары и оставьте для каждого остатка наибольший результат.
- Ответ — наибольшее
best[r]при для условия «не делится» иbest[0]для условия «делится». - Короткий путь для «не делится»: сумма больших чисел пар; если делится на , вычтите наименьшую разность чисел пары, которая не делится на .
Остаток суммы
Остаток от деления суммы на равен остатку от деления суммы остатков слагаемых. Поэтому, чтобы знать, делится ли итоговая сумма на , не нужно помнить сами слагаемые: достаточно остатка суммы. Сумм с разными остатками всего , а не . В Python остаток — x % k: операции с целыми числами.
Пример
Найдите остаток от деления на 3, не складывая числа.
- 1.: сумма цифр 10 даёт остаток 1.
- 2.: сумма цифр 26 даёт остаток 2.
- 3.. Проверка: , . Программа печатает 1 2 0 0.
Ответ:
Таблица лучших сумм по остаткам
Динамическое программирование — метод, в котором задачу решают по шагам и хранят лучшие промежуточные результаты. Здесь промежуточный результат — словарь best: для каждого остатка наибольшая сумма с этим остатком после прочитанных пар. Из двух сумм с одним остатком меньшая не нужна: всё, что можно прибавить к ней, можно прибавить и к большей, а остаток выйдет тот же.
Для новой пары строят новый словарь: каждую сумму из best складывают с первым и со вторым числом пары и для каждого остатка оставляют наибольшую. В словаре не больше записей, поэтому одна пара стоит не больше действий, а весь файл — . Метод работает при любом условии на остаток и для троек чисел.
Пример
Даны пары (1, 3), (5, 12), (6, 9). Выберите из каждой пары одно число так, чтобы сумма не делилась на 3 и была наибольшей.
- 1.Начало: . Пара (1, 3): суммы 1 и 3, словарь .
- 2.Пара (5, 12): из 1 получаем 6 и 13, из 3 — 8 и 15. По остаткам: .
- 3.Пара (6, 9): из 15 — 21 и 24, из 13 — 19 и 22, из 8 — 14 и 17. Словарь .
- 4.Наибольшая сумма с ненулевым остатком — 22, это . Программа печатает три словаря и 22.
Ответ:
Короткий путь: замена в одной паре
Для условия «сумма не делится на » возьмите из каждой пары большее число. Их сумма — наибольшая из возможных. Если не делится на , это ответ. Если делится, в какой-то паре придётся взять меньшее число. Замена в паре уменьшает сумму на разность чисел пары.
Сумма перестаёт делиться на , только если общее уменьшение не делится на . Разность, кратная , остаток не меняет. Поэтому любой подходящий выбор меняет хотя бы одну пару, разность которой не делится на , и теряет не меньше этой разности. Одна замена в паре с наименьшей такой разностью теряет меньше всего. Ответ: , где — наименьшая разность пары, которая не делится на . Нулевая разность делится на и не подходит. Программа ниже делает один проход по файлу.
f = open('27_A.txt')k = 3n = int(f.readline())s = 0dmin = Nonefor i in range(n): a, b = map(int, f.readline().split()) s += max(a, b) d = abs(a - b) if d % k != 0 and (dmin is None or d < dmin): dmin = dif s % k == 0: s -= dminprint(s)
Пример задания
Открытый банк ФИПИ
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.