Ctrl K

Сумма самых тесных разрывов

Сложная
Дан массив целых чисел values и число size. Будем выбирать из массива группы ровно по size элементов (элементы с разными индексами — разные, даже если значения совпадают). Теснота группы — это наименьшая абсолютная разность между двумя её элементами. Верните сумму теснот по всем таким группам. Ответ может быть большим, верните его по модулю 10⁹ + 7.
Пример 1
values=[1, 4, 6], size=2 → 10

Пар три: {1, 4} с разрывом 3, {1, 6} с разрывом 5 и {4, 6} с разрывом 2. Сумма 3 + 5 + 2 = 10.

Пример 2
values=[5, 1, 3, 9], size=3 → 10

Тройки: {1, 3, 5} → 2, {1, 5, 9} → 4, {3, 5, 9} → 2, {1, 3, 9} → 2. Сумма 10.

Пример 3
values=[7, 7, 2], size=3 → 0

Единственная тройка содержит две семёрки, её наименьший разрыв равен 0.

Ограничения
  • 2 ≤ len(values) ≤ 50
  • -10⁸ ≤ values[i] ≤ 10⁸
  • 2 ≤ size ≤ len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКоробка в коробке СложнаяСтрогий подъём из запасных чисел СложнаяСамый выгодный набор подработок СложнаяСамый длинный спуск прыжками СложнаяНаибольшее число, кратное трём Сложная
загружаем Python…
Вход
values=[1, 4, 6], size=2
Ожидается
10

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 116 тестов на сервере, включая скрытые.