Ulične Lampe

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

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 N lampi, na pozicijama 1,2,\cdots,N i distanca između svake dve susedne je 1. Upaljena lampa na poziciji x može da obasja lampe na pozicijama x-1,x,x+1. 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 N (1\leq N\leq 100000), koji označava broj lampi.

U drugom redu standardnog ulaza nalazi se niska S dužine N, gde je S_i=1 ako je lampa i na početku upaljena, a S_i=0 ako je ako je lampa i 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 1010010 gde je svaka lampa osvetljenja: 1,2 lampom na poziciji 1, 2,3,4 lampom na poziciji 3 i 5,6,7 lampom na poziciji 6. Stoga je odgovor u ovom slučaju 1.


Comments

There are no comments at the moment.