Олимпиадный тренинг

Задача . fipi-549B82


Задача

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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя