8438번 - Dyzio 다국어

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 (0) i jedynek (1). 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?

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).

Pierwszy wiersz wejścia zawiera liczbę całkowitą n (1 ≤ n ≤ 20000). 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 n - opis sposobu cięcia sznurka dostarczony przez Dyzia.

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.