Ctrl K

Осада: залпы по стенам

Сложная
Крепость защищают несколько стен, у стены i запас брони armor[i]. Катапульта стреляет залпами. Каждым залпом нужно выбрать одну стену: она теряет direct единиц брони, а **все остальные** стены теряют по splash единиц от разлёта осколков. Стена пала, когда её броня стала нулевой или отрицательной (залпы по уже павшим стенам тоже разрешены). Верните наименьшее число залпов, после которых пали все стены.
Пример 1
armor=[5, 9, 2], direct=5, splash=2 → 3

Два залпа по стене 1: броня становится [1, -1, -2]. Третий залп по стене 0 даёт [-4, -3, -4] — все стены пали. Двух залпов не хватит: стена 1 получила бы самое большее 10 урона, но тогда стена 0 получила бы лишь 4.

Пример 2
armor=[3, 3], direct=3, splash=1 → 2

Первый залп по стене 0: [0, 2]. Второй — по стене 1: [-1, -1].

Пример 3
armor=[4], direct=7, splash=1 → 1

Одна стена, один залп в упор снимает 7 единиц брони.

Ограничения
  • 1 ≤ armor.length ≤ 10⁵
  • 1 ≤ armor[i] ≤ 10⁹
  • 1 ≤ splash < direct ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОбщая медиана двух массивов СложнаяМинимум в сдвинутом массиве с повторами СложнаяРамка вокруг кляксы СложнаяМеньшие справа СложнаяСуммы отрезков в заданной полосе Сложная
загружаем Python…
Вход
armor=[5, 9, 2], direct=5, splash=2
Ожидается
3

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