0 до точки length. В каждой целой точке 0, 1, ..., length стоит дождеватель, всего их length + 1. Дождеватель в точке i, если его включить, поливает отрезок [i - reach[i], i + reach[i]].
Включите как можно меньше дождевателей так, чтобы весь газон [0, length] оказался полит, и верните их количество. Если полить газон целиком нельзя, верните -1.
Полив за пределами газона не мешает и не помогает.length=6, reach=[1, 0, 3, 0, 0, 1, 0] → 2
Дождеватель в точке 2 поливает отрезок [-1, 5], а в точке 5 — [4, 6]. Вместе они покрывают весь газон [0, 6]; одного дождевателя не хватит.
length=4, reach=[1, 0, 0, 0, 1] → -1
Даже если включить всё, отрезок между точками 1 и 3 останется сухим.
length=3, reach=[0, 0, 5, 0] → 1
Дождеватель в точке 2 сам по себе достаёт от -3 до 7.
length ≤ 10⁴len(reach) = length + 1reach[i] ≤ 100length=6, reach=[1, 0, 3, 0, 0, 1, 0]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 87 тестов на сервере, включая скрытые.