Školsko natjecanje iz informatike / Srednja škola / Druga podskupina (3. i 4. razred) - 3. zadatak (2021)

Mirkov najnoviji izum, računalni procesor kodnog imena mirkoprocesor, računa s binarnim nizovima duljine n bitova.

Instrukcije ovog neobičnog procesora su sljedeće:

• lijevi flip k – mijenja se prvih (lijevih) k bitova niza tako da nule postaju jedinice, a jedinice postaju nule;
• desni flip k – mijenja se zadnjih (desnih) k bitova niza tako da nule postaju jedinice, a jedinice postaju nule;
• flip k – mijenja se k-ti bit niza (iz nule u jedinicu ili obrnuto).

Pritom broj k nije fiksan nego se proizvoljno bira za pojedinu instrukciju.

Zadan je neki niz od n bitova koji Mirko uz pomoć svog procesora želi anulirati, tj. promijeniti ga tako da se sastoji samo od nula.

Napišite program koji će reći Mirku koliki je minimalan broj instrukcija koje na tom nizu treba izvesti da se dobije niz od n nula.

ULAZNI PODACI

U prvom retku nalazi se prirodan broj n (2 ≤ n ≤ 1000), duljina niza.

U drugom retku nalazi se zadani niz od n bitova (znakova 0 ili 1), bez razmaka.

IZLAZNI PODACI

U prvi redak ispišite traženi broj instrukcija.

Primjeri test podataka

Ulaz

9
110010011

Izlaz

3

Objašnjenje

Objašnjenje prvog primjera: možemo izvesti lijevi flip 2, flip 5 i desni flip 2.

Ulaz

12
000111000111

Izlaz

3