Ctrl K

Загрузить фургон доставки

Лёгкая
Курьер грузит фургон ящиками. Есть несколько видов ящиков: crates[i] = [count, per_crate] означает, что ящиков этого вида count штук и в каждом лежит per_crate товаров. В фургон помещается не больше capacity ящиков (любых видов вперемешку). Ящики не вскрывают — каждый берётся целиком или не берётся. Верните наибольшее число товаров, которое можно увезти за один рейс.
Пример 1
crates=[[3, 2], [1, 7], [4, 5]], capacity=5 → 27

Берём ящик по 7 и все четыре ящика по 5: 7 + 4 · 5 = 27.

Пример 2
crates=[[2, 4], [2, 3]], capacity=10 → 14

Места больше, чем ящиков, поэтому грузим всё: 2 · 4 + 2 · 3 = 14.

Пример 3
crates=[[5, 1], [1, 9], [2, 6]], capacity=2 → 15
Ограничения
  • 1 ≤ len(crates) ≤ 1000
  • 1 ≤ count, per_crate ≤ 1000
  • 1 ≤ capacity ≤ 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКуски торта для гостей ЛёгкаяСила слабейшего в паре ЛёгкаяТреугольник из палочек ЛёгкаяСмены знака ради большей суммы ЛёгкаяСобрать рюкзак Лёгкая
загружаем Python…
Вход
crates=[[3, 2], [1, 7], [4, 5]], capacity=5
Ожидается
27

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