Решение: Максимальная сумма по остаткам
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек $N$ ($1 \leq N \leq 1\,000\,000$). Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $12\,000$.
Для обработки файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.
Решение по шагам
5 шаговПеребор всех вариантов выбора одного числа из каждой тройки имеет экспоненциальную сложность, поэтому для файла B он непригоден.
Состояние динамического программирования определяется остатком текущей суммы по модулю $109$. Для каждого остатка сохраняется максимальная достижимая сумма.
При обработке очередной тройки из каждого старого состояния рассматриваются три перехода — по одному для каждого числа тройки. Переходы выполняются в новый массив, чтобы из одной тройки нельзя было выбрать более одного числа.
После обработки всех троек выбирается максимальная сумма с остатком, отличным от нуля. Алгоритм работает за $O(109 \cdot 3N)$ времени и использует $O(109)$ памяти.
Числовые значения для файлов A и B невозможно вычислить без самих приложенных файлов с исходными данными.
Точные два числа определить невозможно: файлы A и B не приложены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Хранить только одну максимальную сумму без учёта её остатка по модулю $109$.
Разрешить выбрать несколько чисел из одной тройки при обновлении массива состояний.
Выбрать сумму с остатком $0$, хотя она должна не делиться на $109$.
Использовать перебор всех вариантов для файла B.