== include(page="template/taskheader" task_id="leduri") ==
Am un cablu cu $N$ leduri (numerotate de la $1$ la $N$) aşezate echidistant. Iniţial, unele leduri sunt aprinse, iar altele sunt stinse. Ledurile sunt legate între ele astfel încât atingerea fiecărui led produce modificarea atât a stării lui, cât şi a ledurilor vecine lui. Deci, dacă se atinge ledul i $(2 ≤ i ≤ N-1)$ atunci se modifică stările ledurilor $i-1$, $i$ şi $i+1$. Dacă se atinge ledul $1$, atunci se modifică stările ledurilor $1$ şi $2$, iar dacă se atinge ledul $N$, atunci se modifică stările ledurilor $N-1$ şi $N$. Vreau să modific starea ledurilor astfel încât să semene cu cablul cu $N$ leduri pe care îl are Ionuţ, prietenul meu (două cabluri seamănă dacă pentru orice $i=1..N$ stările ledurilor de pe poziţia i sunt identice).
h2. Cerinţă
Cunoscând cum arată cablul lui Ionuţ, ajutaţi-mă să determin numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca şi cablul lui Ionuţ.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $leduri.in$ conţine pe prima linie numărul natural $N$.
Pe a doua linie sunt $N$ cifre binare separate prin câte un spaţiu reprezentând stările ledurilor de pe cablul meu. Cifra de pe poziţia $i$ este $0$ dacă ledul $i$ este stins, respectiv este $1$ dacă ledul $i$ este aprins $(i=1..N)$.
Pe a treia linie sunt $N$ cifre binare separate prin câte un spaţiu, reprezentând stările ledurilor de pe cablul lui Ionuţ.
Fişierul de intrare $leduri.in$ ...
h2. Date de ieşire
Fişierul de ieşire $leduri.out$ va conţine pe prima linie un singur număr natural reprezentând numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca şi cablul lui Ionuţ.
În fişierul de ieşire $leduri.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $Se garantează că pentru toate testele există soluţie.$
* $Pentru teste valorând 30 de puncte, N va fi cel mult 20$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. leduri.in |_. leduri.out |_. Explicaţie |
| 4
1 0 1 0
0 1 1 1
| 2
| O soluţie posibilă este:
Se apasă mai întâi al doilea led: 1 0 1 0 → 0 1 0 0
Se apasă ultimul led: 0 1 0 0 → 0 1 1 1
|
table(example). |_. leduri.in |_. leduri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="leduri") ==
== include(page="template/taskfooter" task_id="leduri") ==
