W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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?
Napisz program, który:
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.
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.
Dla danych wejściowych:
9 110011000
poprawną odpowiedzią jest:
4
Autor zadania: Krzysztof Diks.