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

179. Рейсы для коробок весом 2ᵃ

Средняя

Есть n машин грузоподъёмностью k кг. Нужно перевезти коробки: i-я весит 2^a[i] кг, делить коробки нельзя, каждая весит не больше k.

За один рейс едут все n машин. Верните наименьшее число рейсов, за которое можно перевезти все коробки.

В работе: Отгрузка со склада Ozon партиями: товары упакованы в типовые короба 1, 2, 4, 8 кг, машин в смене фиксированное число.

Пример 1

Ввод
a = [0, 3, 1, 4, 3, 3]
n = 2
k = 17
Вывод
2

Пример из условия: 16 | 8+8+1 в первом рейсе, 8 | 2 во втором.

Пример 2

Ввод
a = [2, 2, 2]
n = 5
k = 4
Вывод
1

Три машины по одной коробке — хватает одного рейса.

Ограничения

  • 1 ≤ длина a ≤ 10⁴
  • 1 ≤ n ≤ 10⁴, 1 ≤ k ≤ 10⁹
  • 0 ≤ a[i] ≤ 29, 2^a[i] ≤ k
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_trips(a, n, k):
Жадный алгоритмУпаковкаСтепени двойкицельO(n)

Источник: Ozon, отборочный контест Route 256, 2024 (репозиторий участника). Условие пересказано своими словами.