Niz

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Podan je niz S dolžine n, ki je sestavljen iz ničel in enic. Radi bi ga spremenili tako, da ne bo vseboval nobenega strnjenega podniza oblike "010". Edina operacija, ki jo smemo uporabiti, je negacija posameznih bitov (tj. sprememba znaka '1' v znak '0' ali sprememba znaka '0' v znak '1'). Kolikšno je minimalno število operacij, ki jih potrebujemo, da niz S spremenimo tako, da v njem ne bo nobenega strnjenega podniza "010"?

Vhodni podatki

V prvi vrstici je podano število n, tj. dolžina niza S. V drugi vrstici je podan niz S, ki je sestavljen iz ničel in enic.

Omejitve vhodnih podatkov

  • 1 \leq n \leq 10^5

Izhodni podatki

Izpišite eno število – minimalno število potrebnih operacij.

Primer

Vhod

7
0101010

Izhod

2

Komentar

V zgornjem primeru z dvema operacijama dobimo npr. niz "0001110", ki ne vsebuje podniza "010".

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task