Ctrl K

Лягушка переходит реку

Сложная
Лягушка переправляется через реку по камням. Позиции камней заданы строго возрастающим массивом stones; лягушка сидит на первом камне (позиция 0) и хочет попасть на последний. Прыгать можно только вперёд и только на камни — в воду нельзя. Первый прыжок — ровно на 1 единицу. Если предыдущий прыжок был длиной k, следующий может быть длиной k - 1, k или k + 1 (длина всегда положительна). Верните True, если лягушка может добраться до последнего камня, иначе False.
Пример 1
stones=[0, 1, 2, 4, 7] → True

Прыжки 1, 1, 2 и 3: каждый следующий отличается от предыдущего не больше чем на 1.

Пример 2
stones=[0, 2] → False

Первый прыжок обязан быть длиной 1, а на позиции 1 камня нет.

Пример 3
stones=[0, 1, 3, 4, 8] → False

Лягушка доберётся до камня 4, но оттуда сможет прыгнуть не дальше чем на 2, а до 8 — 4 единицы.

Ограничения
  • 2 ≤ len(stones) ≤ 2000
  • 0 ≤ stones[i] ≤ 2³¹ - 1
  • stones[0] = 0
  • stones строго возрастает
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВода между стенами СложнаяСамый большой горящий блок СложнаяПрибыль за две сделки СложнаяВсе способы расставить пробелы СложнаяПереход через пещеру Сложная
загружаем Python…
Вход
stones=[0, 1, 2, 4, 7]
Ожидается
True

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