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

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 103 записей, в файле B — 1000000. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

Из каждой строки сначала выбираем максимум. Их сумма T — верхняя граница для любого допустимого выбора. Если T не делится на 109, она уже является ответом.

Если T делится на 109, нужно уменьшить сумму так, чтобы потеря не делилась на 109. Для каждой строки рассматриваем обе альтернативы максимуму; потеря равна максимум минус выбранное число. Среди всех положительных потерь с ненулевым остатком выбираем наименьшую d. Замена в одной строке даёт T − d с нужным остатком.

Почему нескольких замен не нужно: их потери неотрицательны. Если общая потеря имеет ненулевой остаток, хотя бы одно слагаемое тоже имеет ненулевой остаток. Оно не меньше d, значит и общая потеря не меньше d. Одиночная замена на d достигает этой нижней границы. Проверяем и среднее, и наименьшее число строки: ближайшее по величине число может дать запрещённую кратную потерю, а другое — подходящую.

Распакуем архив и положим указанные в программе текстовые файлы рядом с ней. Программа печатает результат для A, затем для B:

from array import array

def solve(name):
    mod = 109
    total = 0
    loss = None
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        for _ in range(n):
            row = tuple(map(int, f.readline().split()))
            high = max(row)
            total += high
            for value in row:
                delta = high - value
                if delta % mod != 0 and (loss is None or delta < loss):
                    loss = delta
    if total % mod != 0:
        return total
    return total - loss

print(solve('613_27_A.txt'), solve('613_27_B.txt'))

Время O(N), дополнительная память O(1). Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Файл B: в строке 773482 записаны 7671, 280, 7998. Заменяем 7998 на 280, потеря 7718. Получаем 8819096478 − 7718 = 8819088760; потеря не делится на 109.

Независимая динамика по всем остаткам, которая на каждом шаге рассматривает все три выбора, подтвердила ответ.

Ответ: 784594 8819088760.