Chú chó Scooby Doo


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Tichpx nuôi một chú chó rất thông minh có tên là Scooby Doo. Nhà Tichpx cạnh một con suối để sang bên kia bờ suối người ta xếp những hòn đá to liền nhau để đi qua. Chú chó Scooby Doo nhà Tichpx có thể nhẩy từ được từ hòn đá này sang hòn đá kia nếu 2 hòn đá cạnh nhau hoặc cùng lắm là cách một hòn đá. Mấy hôm nay đầu mùa hạ nước mưa dâng lên làm một số hòn đá bị ngập nước không thể đứng lên được. Mặc dù rất thông minh nhưng Scooby Doo vẫn không biết có sang được suối không hoặc nếu sang được thì bước nhẩy thế nào để số bước nhẩy là ngắn nhất. Bạn hãy lập trình giúp chú chó có câu trả lời nhé

Input

Dòng đầu là số nguyên dương n \((1 \le n \le 10^5)\) là số hòn đá đặt ngang qua con suối thành một đường thẳng lần lượt từ viên thứ 1 tới viên thứ n

Dòng tiếp theo n là các giá trị 0, 1 thể hiện là hòn đá thứ i nếu có giá trị 0 là không ngập nước chú chó có thể nhẩy lên hòn đá đó ngược lại nếu có giá trị 1 thì hòn đá bị ngập nước và không thể đặt chân lên được

Output

Số bước nhẩy ít nhất để chú chó đứng ở hòn thứ nhất nhẩy lên hòn thứ n (hai hòn đá này luôn luôn không bị ngập nước). Nếu không nhẩy được đến hòn đá thứ n in ra "khong qua duoc suoi"

Ví dụ 1

Input

7
0 0 1 0 0 1 0

Output

4

Giải thích: Từ hòn 1 nhẩy sang hòn 2; từ hòn 2 nhẩy sang hòn 4; từ hòn 4 nhẩy sang hòn 5; từ hòn 5 nhẩy sang hòn 7 vì vậy tất cả có 4 bước

Ví dụ 2

Input

7
0 0 1 1 0 1 0

Output

khong qua duoc suoi
tichpx

Comments


  • -1
    vtn  commented on Feb. 11, 2019, 8:17 a.m.

    đặt sai số 1 mà gửi tận 5 lần mới đúng