leduri

Time limit: 0.1s Memory limit: 16MB Input: leduri.in Output: leduri.out

Am un cablu cu NN leduri (numerotate de la 11 la NN) 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 ii (2iN12 \leq i \leq N-1) atunci se modifică stările ledurilor i1i-1, ii și i+1i+1. Dacă se atinge ledul 11, atunci se modifică stările ledurilor 11 și 22, iar dacă se atinge ledul NN, atunci se modifică stările ledurilor N1N-1 și NN.

Vreau să modific starea ledurilor astfel încât să semene cu cablul cu NN leduri pe care îl are Ionuț, prietenul meu (două cabluri seamănă dacă pentru orice i=1Ni=1 \dots N stările ledurilor de pe poziția ii sunt identice).

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ț.

Date de intrare

Fișierul de intrare leduri.in conține pe prima linie numărul natural NN. Pe a doua linie sunt NN cifre binare separate prin câte un spațiu reprezentând stările ledurilor de pe cablul meu. Cifra de pe poziția ii este 0 dacă ledul ii este stins, respectiv este 11 dacă ledul ii este aprins (i=1Ni=1 \dots N). Pe a treia linie sunt NN cifre binare separate prin câte un spațiu, reprezentând stările ledurilor de pe cablul lui Ionuț.

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ț

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000
  • Se granteaza ca pentru toate testele există soluție.

Exemplu

leduri.in

4
1 0 1 0
0 1 1 1

leduri.out

2

Explicație

O soluție posibilă este:

  1. Se apasă mai întâi al doilea led: 101001001 0 1 0 \rightarrow 0 1 0 0;
  2. Se apasă ultimul led: 010001110 1 0 0 \rightarrow 0 1 1 1.

Log in or sign up to be able to send submissions!