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