Максимальная сумма по остаткам
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек $N$ ($1 \leq N \leq 1\,000\,000$). Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $12\,000$.
Для обработки файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.
Условие как в банке ФИПИ — открыть и сверить
|
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k = 109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит Пример организации исходных данных во входном файле: 6 1 3 7 5 12 6 6 9 11 5 4 8 3 5 4 1 1 1 Для указанных входных данных, в случае, если k = 5, значением искомой суммы является число 44. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Как изменяется остаток суммы при добавлении одного выбранного числа?
2Наводящая — какие числа считатьуровень 2 из 3
Для каждого возможного остатка по модулю $109$ храните максимальную сумму, которую можно получить после обработки некоторого количества троек.
3Прямая — фактически решениеуровень 3 из 3
Инициализируйте $dp[0] = 0$, остальные значения — как недостижимые. Для каждой тройки создайте новый массив: $new\_dp[(r + a_i) \bmod 109] = \max(new\_dp[(r + a_i) \bmod 109], dp[r] + a_i)$ для каждого из трёх чисел $a_i$. После обработки всех троек ответом будет максимум среди $dp[r]$ при $r \ne 0$.