Задание №27 — Оптимальный алгоритм для большого количества данных

Решение:

Сначала забудем про делимость и возьмём из каждой пары большее число. Полученная сумма $S$ — наибольшая из всех возможных, поэтому если она не делится на 3, то она и есть ответ.

Пусть $S$ делится на 3. Тогда в некоторых парах придётся взять меньшее число. Замена в паре $(a,b)$ уменьшает сумму ровно на $d=|a-b|$, а замены в нескольких парах — на сумму соответствующих разностей. Итоговая сумма $S-\sum d$ не делится на 3 тогда и только тогда, когда $\sum d$ не кратна 3 (ведь само $S$ кратно 3). Но если бы все слагаемые в $\sum d$ были кратны 3, то и вся сумма была бы кратна 3; значит, хотя бы одна разность $d$ не кратна 3, и потому $\sum d \ge d_{\min}$, где $d_{\min}$ — наименьшая положительная разность, не кратная 3. Эта оценка достижима: достаточно поменять выбор в одной-единственной паре. Итак, ответ равен $S$, если $S$ не делится на 3, и $S-d_{\min}$ иначе.

Алгоритм линейный: один проход по файлу, в котором накапливаются $S$ и $d_{\min}$.

def solve(name, m):
    f = open(name)
    n = int(f.readline())
    s = 0                       # сумма больших чисел из каждой пары
    best = 10**9                # минимальная «допустимая» разность
    for _ in range(n):
        a, b = map(int, f.readline().split())
        s += max(a, b)
        d = abs(a - b)
        if d > 0 and d % m != 0:
            best = min(best, d)
    if s % m != 0:
        return s
    return s - best

print(solve('A.txt', 3), solve('B.txt', 3))

Файл A: сумма больших чисел равна $127341$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $214$, поэтому ответ $127341 - 214 = 127127$.Файл B: сумма больших чисел равна $399762096$ и делится на 3. Наименьшая ненулевая разность внутри пары, не кратная 3, равна $16$, поэтому ответ $399762096 - 16 = 399762080$.Ответ: 127127 399762080