Решение: Максимальная сумма без делимости
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек $N$ ($1 \leq N \leq 1\,000\,000$). Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $12\,000$.
Для приведённого в условии примера, если $k = 5$, искомая сумма равна 44. В ответе укажите значение искомой суммы для файла A, затем для файла B. Для обработки файла B нельзя использовать перебор всех возможных вариантов.
Вложенные файлы с исходными данными в предоставленном наборе отсутствуют, поэтому числовые значения ответов для файлов A и B определить невозможно.
Решение по шагам
4 шагаСостояние динамического программирования определяется остатком текущей суммы при делении на $109$. Для каждого остатка сохраняется наибольшая возможная сумма.
$$dp[r] = \text{максимальная сумма с остатком } r$$При обработке очередной тройки перебираем только три варианта выбора. Для каждого прежнего остатка $r$ и числа $x$ из тройки обновляем состояние с новым остатком.
$$new[(r+x) \bmod 109] = \max(new[(r+x) \bmod 109],\, dp[r]+x)$$После обработки всех троек запрещён остаток $0$. Поэтому ответом является максимум среди состояний с остатками от $1$ до $108.
$$\max\{dp[r]\mid 1 \leq r < 109\}$$Численные ответы для файлов A и B нельзя вычислить без самих файлов с исходными данными.
Численные значения ответов для файлов A и B не определяются без приложенных входных файлов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Хранить только одну максимальную сумму и потерять информацию об остатке.
Разрешить выбирать несколько чисел из одной тройки или не выбирать ни одного.
Включить сумму с остатком 0 в итоговый максимум.
Использовать перебор всех вариантов, имеющий экспоненциальную сложность.