Тяжело · 5 очковЕГЭ задание 27Остатки по модулюЭффективный алгоритм1 решили

ЕГЭ №27: минимальная сумма пары на расстоянии ≥ d, кратная K

Дан список целых чисел nums и числа d, k. Среди всех пар индексов i < j с расстоянием j - i >= d и суммой nums[i] + nums[j], кратной k, нужно найти минимальную такую сумму. Если подходящей пары нет — вернуть None.

Решение должно быть за O(n): идём слева направо; для каждого правого элемента nums[j] берём ранее встреченный (с учётом ограничения по расстоянию) элемент с остатком (k - nums[j] % k) % k, храня минимум по каждому остатку. Ответ обязан совпадать с наивным перебором за O(n^2).

Вход: nums — список целых чисел; d >= 1; k >= 1. Выход: целое число (минимальная сумма) или None.

Примеры:

min_pair_sum_div([3, 1, 4, 1, 5, 9, 2, 6], 2, 3) -> 3
min_pair_sum_div([10, 20, 30, 40], 1, 10)        -> 30
min_pair_sum_div([1, 2, 3], 5, 2)                -> None

Теория: Задание 27: эффективный алгоритм анализа последовательности

Курс по теме: Python с нуля — 8 уроков, по шагам и с проверкой

Python
def min_pair_sum_div(nums, d, k):
    # ваш код
    pass

Нажми «Проверить код» — прогоним тесты и покажем, что не так, если не пройдут.

Ctrl↵ проверить

Проверять можно без входа. , чтобы решение и очки сохранились.