Задача №27 ЕГЭ по информатике регулярно просит обработать большой файл чисел и найти нечто «максимальное/минимальное» с условием кратности. Наивный перебор пар за O(N²) на реальных данных не успеет. Ниже — понятный, «рабочий» алгоритм в одну проходку, которым мои ученики стабильно берут баллы.
Формулировка типового задания
Дан файл из N натуральных чисел. Требуется найти максимальную сумму пары чисел, кратную K (например, 120). Если такой пары нет — вывести 0 (или сообщить, что не существует).
Вариации: «минимальная сумма, кратная K», «сумма, дающая остаток R», «пара/тройка чисел». Принцип везде схож.
Ключевая идея: работаем с остатками
Сумма двух чисел кратна K, когда (x % K) + (y % K) ≡ 0 (mod K).
Значит, числу с остатком r подходит число с остатком (K − r) % K.
Идея алгоритма: в один проход держим для каждого остатка лучший кандидат (например, максимальное число с этим остатком). Встречая новое число x, сразу пытаемся составить пару с «дополняющим» остатком и обновляем ответ.
Пошаговый алгоритм (максимальная сумма, кратная K)
Пусть best[r] — максимальное число среди уже просмотренных, дающее остаток r при делении на K.
ans — лучший ответ (максимальная сумма), изначально 0.
Для каждого числа x из файла:
- r = x % K
- c = (K - r) % K — дополняющий остаток
- Если best[c] существует, кандидат в ответ: x + best[c].
Обновляем ans = max(ans, x + best[c]). - Обновляем хранилище: best[r] = max(best[r], x).
Сложность: O(N + K) по времени и O(K) по памяти. Идеально для больших N.
⚠️ Специальные случаи «0» и «K/2» (когда K чётное) автоматически корректно обрабатываются формулой c = (K - r) % K. Никаких отдельных веток не нужно.
Почему это корректно
- Любая пара, чья сумма кратна K, состоит из остатков r и K−r (включая r = 0 и, при чётном K, r = K/2, где оба числа имеют одинаковый остаток).
- Мы всегда храним лучших представителей каждого остатка; значит, максимальная возможная сумма с данным x будет получена через best[c].
- Один проход гарантирует, что каждая потенциальная пара будет рассмотрена, когда обрабатывается второй её элемент.
Реализация на Python (стиль ЕГЭ)
Вариант 1: читаем из файла построчно
Вариант 2: если числа в одной строке (иногда встречается)
Что любят проверять:
- Умение не хранить весь массив (стриминговая обработка).
- Правильная работа с остатками и «пустыми» остатками.
- Корректность границ и инициализаций (не путайте 0 и «не существует»).
Типичные ошибки (и как их не допустить)
- Перебор всех пар O(N²).
На больших файлах не успеет. Держите best[r] и работайте в один проход. - Неверная инициализация хранилища.
Пустые ячейки лучше заполнять очень маленьким числом, а не нулём, чтобы не «склеить» ложные пары. - Забыли обновить best[r] после проверки пары.
Порядок важен: сначала пробуем сделать пару с x, потом кладём x как кандидата для будущих чисел. - Сломали случай r = 0 или r = K/2.
Не выделяйте их отдельно — формула с c = (K - r) % K всё делает сама. - Путаем «максимальную сумму кратную K» с «максимальной суммой вообще».
Проверяйте условие кратности только через остатки, а не «на глаз».
Как превратить решение «на пару» в решение «на тройку»
Иногда просят минимальную сумму, кратную K, или сумму с конкретным остатком R. Достаточно хранить:
- Для «максимальной суммы» — максимум по каждому остатку.
- Для «минимальной суммы» — минимум по каждому остатку (инициализируйте «плюс бесконечностью»).
- Для «остатка R» — подбираем вторую половину так, чтобы (r + r2) % K == R, то есть r2 = (R - r) % K.
Пример (минимальная сумма, кратная K):
Частые модификации в Сдаче №27 и как к ним готовиться
- Ограничение расстояния между элементами («индексы должны отличаться не менее чем на D»):
храните best[r] на расстоянии — поддерживайте скользящее окно: сначала вычитаете элемент, который «вышел» за дистанцию, затем добавляете текущий. - Тройки/кортежи чисел:
храните промежуточные лучшие значения: для троек — «лучшие пары по остаткам», и комбинируйте с текущим x. - Смешанные условия («кратна K и не кратна M»):
фильтруйте кандидатов по двум условиям или храните отдельные best под каждый критерий.
Мини-проверка понимания (с ответом)
Задача. K=7. На вход пришли числа: 10, 14, 20, 3.
Остатки: 3, 0, 6, 3. Лучшие по остаткам растут так:
- x=10 (r=3): пары нет → best[3]=10
- x=14 (r=0): дополняющий c=0 → пары нет (best[0] пуст) → best[0]=14
- x=20 (r=6): c=1 → пары нет → best[6]=20
- x=3 (r=3): c=4 → пары нет → best[3]=max(10,3)=10
Максимальной суммы, кратной 7, нет (0). Если бы между вторым и четвёртым было число с остатком 4, ответ бы обновился.
⚠️ Важно: разбор выше — это прототип №27 из вариантов прошлых лет. Сейчас формулировки поменялись: даны кластеры фрагментов звёздного неба, с которыми в зависимости от условия потребуется поработать.
В телеграмм-канале я разбираю актуальные изменения по свежим вариантам, показываю, как адаптировать алгоритм «по остаткам» под новые условия и где чаще всего теряются баллы.