Cod sursa(job #2749131)

Utilizator mariusn01Marius Nicoli mariusn01 Data 5 mai 2021 10:38:46
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
/**
generez toate sirurile de 0 si 1 cu exact care 2 de 1 vecini
3 4 0 1 0 6 7 1 2 1
0 1 1 0 0 1 1 0 1 1
**/

#include <fstream>

using namespace std;
int v[100010], x[100010];
int n, sol, i;
int cont(int pas) {
    if (pas >= 3) {
        if (x[pas] == 1 && x[pas-1] == 1 && x[pas-2] == 1)
            return 0;
        if (x[pas] == 0 && x[pas-1] == 1 && x[pas-2] == 0)
            return 0;
    }
    return 1;
}

void backtrack(int pas) {
    /// toate sirurile de lungime n cu 0 si 1
    /// cu exact cate 2 de 1 vecini (circulare)
    if (pas > n) { /// sol are n elemente

        if (x[n] == 1 && x[n-1] == 1 && x[1] == 1)
            return;
        if (x[n] == 1 && x[1] == 1 && x[2] == 1)
            return;
        if (x[n] == 1 && x[1] == 0 && x[n-1] == 0)
            return;
        if (x[1] == 1 && x[2] == 0 && x[n] == 0)
            return;

        int suma = 0;
        for (int i=1;i<=n;i++)
            if (x[i] == 1)
                suma += v[i];

        if (suma > sol)
            sol = suma;


    } else {
        for (int i=0;i<=1;i++) { /// orice element din solutie poate fi 0 sau 1
            x[pas] = i;
            if (cont(pas))
                backtrack(pas+1);
        }
    }
}

int main () {
    ifstream fin ("oo.in");
    ofstream fout("oo.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    backtrack(1);
    fout<<sol;
    return 0;
}