Войти Регистрация
Алгоритмы

91. Сколько раскладок заказов по курьерам

Сложная

В час пик в даркстор Яндекс Лавки пришло total заказов. На смене n курьеров, i-й может взять от 0 до limits[i] заказов.

Раскладка — сколько заказов досталось каждому курьеру; все total заказов должны быть розданы. Верните число раскладок по модулю 10⁹ + 7. Если раздать нельзя, ответ 0.

В работе: Подсчёт вариантов распределения ресурса с ограничениями: слоты, бюджеты, квоты.

Пример 1

Ввод
limits = [2, 1, 3]
total = 4
Вывод
5

Например (2, 1, 1), (0, 1, 3), (1, 0, 3) — всего 5 раскладок.

Пример 2

Ввод
limits = [1, 1]
total = 3
Вывод
0

Двое возьмут максимум 2 заказа.

Ограничения

  • 1 ≤ n ≤ 2000
  • 0 ≤ limits[i] ≤ 2000
  • 0 ≤ total ≤ 2000
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def count_splits(limits, total):
ДППрефиксные суммыКомбинаторикацельn2

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.