Cod sursa(job #2068751)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 18 noiembrie 2017 10:52:51
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>

using namespace std;

int pre[500005], v[500005], x[500005], n;

void buildPre() {
    int len = 0, i = 2;
    while(i < n) {
        if(v[len + 1] == v[i]) {
            pre[i ++] = ++ len;
        } else {
            if(len > 0) {
                len = pre[len];
            } else {
                len = 0;
                ++ i;
            }
        }
    }
}

int main() {
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &x[i]);
        if(i > 1) {
            v[i - 1] = x[i] - x[i - 1];
        }
    }

    buildPre();

    int rasp = n - 1;
    for(int p = n - 1; p >= 2; -- p) {
        if(pre[p] > 0 && p % (p - pre[p]) == 0 && (p - pre[p]) > n - 1 - p) {
            bool ok = true;
            for(int i = p + 1, j = 1; i <= n - 1; ++ i, ++ j) {
                if(v[i] != v[j]) {
                    ok = false;
                    break;
                }
            }
            if(ok == true && rasp > p - pre[p]) {
                rasp = p - pre[p];
            }
        }
    }

    printf("%d\n", rasp);
    for(int i = 1; i <= rasp; ++ i) {
        printf("%d\n", v[i]);
    }

    return 0;
}