Как решать задание 27 ЕГЭ по информатике (оптимальная сумма, остатки)?

Задание 27 — самое дорогое и сложное. Классический сюжет: дана последовательность чисел, нужно выбрать пару (или подпоследовательность) с максимальной суммой, делящейся на K, иногда с дополнительными условиями (несоседние, на расстоянии и т.п.).

Две версии данных: A (маленький набор, можно перебором) и B (огромный, нужен эффективный однопроходный алгоритм). Балл за B — за алгоритм без квадратичного перебора.

Ключевая идея — работа с остатками по модулю K. Для каждого нового числа смотришь его остаток x % K, и держишь максимумы по остаткам, чтобы быстро подобрать пару, дающую в сумме кратное K.

# скелет однопроходного решения
import sys
K = 5
best = {}                 # лучший элемент с данным остатком
ans = -1
for x in numbers:         # один проход
    r = x % K
    need = (K - r) % K    # какой остаток нужен в пару
    if need in best:
        ans = max(ans, x + best[need])
    # обновляем максимум по остатку r
    if r not in best or x > best[r]:
        best[r] = x
print(ans)

Стратегия на экзамене: сначала возьми простой перебор для набора A — это уже гарантированный балл:

best = 0
for i in range(n):
    for j in range(i+1, n):
        s = a[i] + a[j]
        if s % K == 0:
            best = max(best, s)

Потом думай над эффективной версией для B.

Частые ошибки:

• лезть сразу в сложный алгоритм и провалить даже A — бери лёгкий балл первым;
• неверно понять условие (несоседние? любая пара? подряд?);
• ошибиться с остатком при отрицательных числах (в Python % уже даёт неотрицательный остаток — это плюс).

На codechick есть разбор задания 27 по шагам.