Задание 27: макс. сумма пары на расстоянии с условием кратности
Задание 27 КЕГЭ требует эффективного алгоритма (за один проход), потому что данных много. Здесь последовательность передаётся списком numbers.
Напишите функцию max_pair_sum_div(numbers, min_dist, divisor), которая возвращает максимальную сумму пары элементов numbers[i] + numbers[j] таких, что:
- индексы отстоят друг от друга не менее чем на
min_dist(то естьj - i >= min_dist, i < j); - сумма делится на
divisorнацело.
Если подходящей пары нет, верните -1. Решение должно работать за один проход (без перебора всех пар).
Идея: идя по j, поддерживаем для каждого остатка по модулю divisor максимальный «разрешённый» элемент слева (среди индексов i ≤ j − min_dist). Для текущего numbers[j] нужен остаток (-numbers[j]) % divisor.
Формат входа: список целых numbers, целые min_dist (≥ 1) и divisor (≥ 1).
Формат выхода: одно целое число — максимальная сумма, или -1.
Пример 1: max_pair_sum_div([1, 5, 3, 9, 2, 6, 4, 8], 3, 3) → 9.
Пример 2: max_pair_sum_div([10, 20, 30, 40, 50], 1, 10) → 90.
def max_pair_sum_div(numbers, min_dist, divisor):
# верните максимальную сумму numbers[i]+numbers[j] при j-i>=min_dist
# и (numbers[i]+numbers[j]) % divisor == 0; если пары нет — -1
pass
