Задание 27 ЕГЭ по информатике · 549B82

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k=109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек N (1≤N≤1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 12 000.
Для приведённого в условии примера, если k=5, искомая сумма равна 44. В ответе укажите значение искомой суммы для файла A, затем для файла B. Для обработки файла B нельзя использовать перебор всех возможных вариантов.
Вложенные файлы с исходными данными в предоставленном наборе отсутствуют, поэтому числовые значения ответов для файлов A и B определить невозможно.

1. Состояние динамического программирования определяется остатком текущей суммы при делении на 109. Для каждого остатка сохраняется наибольшая возможная сумма.
dp[r]=максимальная сумма с остатком r

2. При обработке очередной тройки перебираем только три варианта выбора. Для каждого прежнего остатка r и числа x из тройки обновляем состояние с новым остатком.
new[(r+x) mod 109]=max(new[(r+x) mod 109], dp[r]+x)

3. После обработки всех троек запрещён остаток 0. Поэтому ответом является максимум среди состояний с остатками от 1 до $108.
max{dp[r]∣1≤r<109}

4. Численные ответы для файлов A и B нельзя вычислить без самих файлов с исходными данными.