Задача HOPPER. Исследователи, изучающие интеллект насекомых, провели следующий эксперимент. Длинную ленту разбили на N клеток одинакового размера и на первую клетку посадили кузнечика. Цель кузнечика – достичь последней клетки ленты. Часть клеток ленты закрашены в красный цвет, которого кузнечик боится – на такие клетки он становиться не может. Известно, что первая и последняя клетки ленты никогда не закрашиваются в красный цвет.
Кузнечик перемещается по ленте прыжками. Он может прыгать только из клетки в клетку. Кузнечик может прыгать по ленте как вперед, так и назад.
Сперва кузнечик может перепрыгнуть только на соседнюю клетку. Это прыжок длины 1. После каждого прыжка кузнечик выбирает направление следующего прыжка (вперед или назад), а также может увеличить длину прыжка на одну клетку, уменьшить длину прыжка на одну клетку, либо оставить длину прыжка неизменной. Кузнечик не может прыгать на красные клетки или выпрыгивать за пределы ленты.
Определите, сможет ли кузнечик добраться до последней клетки ленты, и если сможет, то какое наименьшее количество прыжков ему придется для этого совершить.
Технические условия. Напишите программу HOPPER, которая читает с устройства стандартного ввода число N – количество клеток в ленте. Вторая строка ввода содержит последовательность из N нулей и единиц, разделенных пробелами, которая показывает, как раскрашена лента. При этом 0 означает обычную клетку, а 1 – закрашенную в красный цвет. Программа выводит на устройство стандартного вывода одно число – наименьшее количество прыжков, необходимое кузнечику, чтобы достигнуть последней клетки ленты, или число -1, если это невозможно.
Ограничения: 1 < N <= 1000.
Пример
|
Ввод 13 |
Вывод 5 |