== include(page="template/taskheader" task_id="leduri") ==
Poveste şi cerinţă...
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ţ.
h2. Date de intrare
Fişierul de intrare $leduri.in$ ...
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ţ.
h2. Date de ieşire
În fişierul de ieşire $leduri.out$ ...
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ţ.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
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
|
== include(page="template/taskfooter" task_id="leduri") ==
== include(page="template/taskfooter" task_id="leduri") ==
