Ctrl K

Крайние значения маленьких групп

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

Группы из одного элемента дают 8 + 2 + 6 = 16. Пары: {4, 1} → 5, {4, 3} → 7, {1, 3} → 4, всего 16. Ответ 32.

Пример 2
values=[2, 2], limit=1 → 8

Только группы из одного элемента: в каждой минимум и максимум равны 2, итого 4 + 4 = 8.

Пример 3
values=[0, 5, 10], limit=3 → 70
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 0 ≤ values[i] ≤ 10⁹
  • 1 ≤ limit ≤ min(70, len(values))
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНаборы без заданной разницы СредняяНаборы без заданного разрыва СредняяЦепочка кратных СредняяПодмножества с нечётной суммой СредняяНаибольшее число, кратное трём Сложная
загружаем Python…
Вход
values=[4, 1, 3], limit=2
Ожидается
32

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