Dyzio

Limit pamięci: 32 MB

Dyzio jest przyjacielem Jaśka i też lubi zagadki. Oto zagadka, z którą Dyzio przyszedł do Jaśka:

Jaśku, masz tu sznurek, który trzeba pociąć na mniejsze kawałki. Nie powiem Ci wprost, jak to zrobić, ale popatrz na ten ciąg zer () i jedynek (). Jedynka na początku oznacza, że sznurek trzeba przeciąć na pół. Jeśli jednak pierwszą cyfrą byłoby zero, to byłaby to jedyna cyfra w ciągu i oznaczałaby, że nie musisz już nic robić - chcę mieć sznurek w całości. Jeśli jednak musisz przeciąć sznurek, to po pierwszej jedynce zapisałem, co zrobić z lewym kawałkiem (stosując te same reguły, co dla całego sznurka), a następnie zapisałem co zrobić z prawym kawałkiem (cały czas trzymając się tych samych zasad zapisu). Zawsze musisz najpierw pociąć lewy kawałek, a dopiero potem mozesz zabrać się do prawego. A teraz tnij i powiedz, ile minimalnie cięć trzeba wykonać, żeby otrzymać najkrótszy kawałek.

Niestety mama chowa przed Jaśkiem nożyczki, ale szczęśliwie pod ręką był komputer i Jasiek szybko napisał program symulujący cięcie sznurka. Czy Ty też potrafisz napisać taki program?

Zadanie

Napisz program, który:

• wczyta (ze standardowego wejścia) opis sposobu cięcia sznurka,
• policzy, ile minimalnie cięć trzeba wykonać, żeby dostać (pierwszy) najkrótszy kawałek,
• wypisze wynik (na standardowe wyjście).

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą (). W drugim wierszu wejścia zapisano dokładnie jedno słowo zero-jedynkowe (ciąg zer i jedynek bez znaków odstępu między nimi) długości - opis sposobu cięcia sznurka dostarczony przez Dyzia.

Wyjście

Twój program powinien wypisać (na standardowe wyjście) tylko jeden wiersz i zawierający tylko jedną liczbę całkowitą, równą minimalnej liczbie cięć, które trzeba wykonać, żeby dostać najkrótszy kawałek.

Przykład

Dla danych wejściowych:

9
110011000

poprawną odpowiedzią jest:

4

Autor zadania: Krzysztof Diks.