Задание EGEINF028200: Эффективная обработка данных и кластеры

Решение.
Из каждой тройки нужно взять ровно одно число. Требуется максимальная сумма, не делящаяся на 109; файл A и файл B обрабатываем отдельно.
Сначала возьмём максимум каждой тройки и сложим эти числа. Обозначим сумму S. Она не меньше любой другой возможной суммы. Если S не делится на 109, она сразу является ответом.
Если S делится на 109, нужно заменить хотя бы один выбранный максимум. При замене максимума m на число x из той же тройки сумма уменьшается на d = m − x. Эти потери неотрицательны. Замена с потерей, кратной 109, не меняет делимость и сама по себе не помогает.
Найдём минимальную среди всех потерь d, не делящихся на 109. Тогда S − d не делится на 109 и достигается одной разрешённой заменой.
Докажем оптимальность одной замены. Любой другой допустимый набор отличается от набора максимумов некоторыми заменами. Их общая потеря не кратна 109. Значит хотя бы одна из отдельных потерь не кратна 109: иначе их сумма тоже делилась бы на 109. Эта отдельная потеря не меньше найденного минимума d. Все остальные потери неотрицательны, поэтому общая потеря не меньше d. Таким образом, S − d — наибольшая допустимая сумма.
Гарантия существования ответа означает, что при S, кратной 109, подходящая потеря обязательно найдётся. Проверяем обе альтернативы в каждой тройке, а не только второе по величине число.
Программа на Python 3. Файлы 27_A.txt и 27_B.txt сохраняем рядом с программой:

def solve(filename):
    total = 0
    loss = float('inf')
    with open(filename) as f:
        n = int(f.readline())
        for _ in range(n):
            triple = list(map(int, f.readline().split()))
            largest = max(triple)
            total += largest
            for value in triple:
                difference = largest - value
                if difference % 109 != 0:
                    loss = min(loss, difference)
    if total % 109 != 0:
        return total
    return total - loss

print(solve('27_A.txt'), solve('27_B.txt'))

Результаты вычислений:

В файле A исходная сумма уже подходит. Потерю 22 применять не нужно.
Проверка. В файле B заменяем максимум в тройке номер 773482, считая первую тройку после заголовка первой. Эта тройка: 7671, 280, 7998. Замена 7998 на 280 уменьшает сумму на 7718. Потеря 7998 − 7671 = 327 кратна 109 и не подходит.
Получаем 8819096478 − 7718 = 8819088760. Остаток результата при делении на 109 равен 21, то есть условие выполнено. Просмотр всех допустимых потерь подтверждает минимальность 7718; для файла A дополнительно выполнено динамическое программирование по всем 109 остаткам.
Программа читает строки по одной: время O(N), дополнительная память O(1). Целые числа Python сохраняют сумму точно даже для миллиона троек.
Ответ: 784594 8819088760.