U Ulici brestova se već godinama jako strašne stvari dešavaju i, kao posledica toga, njeni stanovnici su sada smrtno uplašeni mraka! Duž Ulice brestova stoji lampi, na pozicijama
i distanca između svake dve susedne je
. Upaljena lampa na poziciji
može da obasja lampe na pozicijama
. Na početku su upaljene neke lampe. Cilj nam je da upalimo još neke lampe, tako da je svaka lampa obasjana bar jednom lampom, i to postići paljenjem što manje novih lampi.
Opis ulaza
U prvom redu standardnog ulaza nalazi se prirodan broj (
), koji označava broj lampi.
U drugom redu standardnog ulaza nalazi se niska dužine
, gde je
ako je lampa
na početku upaljena, a
ako je ako je lampa
na početku ugašena.
Opis izlaza
Na standardni izlaz ispisati jedan ceo broj - najmanji broj novih lampi koje je potrebno upaliti da bi svaka lampa bila obasjana.
Primer ulaza
7
1010000
Primer izlaza
1
Objašnjenje primera
Na početku poslednja lampa nije obasjana nijednom lampom, stoga moramo da upalimo bar jednu lampu. Paljenjem šeste lampte tada dobijemo konfiguraciju gde je svaka lampa osvetljenja:
lampom na poziciji
,
lampom na poziciji
i
lampom na poziciji
. Stoga je odgovor u ovom slučaju
.
Comments
test