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

Cerința

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

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

1 ≤ N ≤ 100000
Se garantează că pentru toate testele există soluție.
Pentru teste valorând 30 de puncte, N va fi cel mult 20

Exemplu

leduri.in

4
1 0 1 0
0 1 1 1

leduri.out

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Leduri:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000000;
int A0[MAXN], A1[MAXN], B[MAXN];
int n;

int transform(int A[]) {
    int ops = 0;

    for(int i = 1; i < n; ++i) {
        if(A[i] != B[i]) {
            A[i] ^= 1;
            A[i + 1] ^= 1;
            A[i + 2] ^= 1;
            ops += 1;
        }
    }
    return ops;
}

int main() {
  freopen("leduri.in", "r", stdin);
  freopen("leduri.out", "w", stdout);
    cin >> n;

    for(int i = 1; i <= n; ++i) {
        cin >> A0[i];
        A1[i] = A0[i];
    }
    for(int i = 1; i <= n; ++i) {
        cin >> B[i];
    }

    A1[1] ^= 1; A1[2] ^= 1;
    int a = transform(A0);
    int b = transform(A1);

    int ans = 1000000;
    if(A0[n] == B[n]) ans = min(ans, a);
    if(A1[n] == B[n]) ans = min(ans, b + 1);

  if(ans == 1000000)
    ans = -1;
    cout << ans << endl;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1686 Leduri

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1686 Leduri de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1686 Leduri