Cod sursa(job #1694921)

Utilizator sucureiSucureiRobert sucurei Data 26 aprilie 2016 11:52:10
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <cstdio>
using namespace std;

const char iname[] = "reguli.in";
const char oname[] = "reguli.out";

const int MAXN = 500010;

long long x[MAXN], a[MAXN];
int n;

void getPrefix()
{
    int dim = 0, poz = 0;
    int pr[MAXN];
    int k = 0;
    pr[1] = 0;
    for(int i = 2; i < n; i++)
    {
        while(k > 0 && a[k+1] != a[i])
            k = pr[k];
        if(a[k+1] == a[i])
            k++;
        pr[i] = k;
        if(k == 1) poz = i - 1;
        if(poz > 0 && k > 0 && (k%poz == 0)) dim = poz;
    }
    if(dim == 0) dim = n-1;
    printf("%d\n",dim);
    for(int i = 1; i <= dim; i++)
        printf("%lld\n", a[i]);
}

int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d", &n);
    scanf("%lld",x);
    for(int i = 1; i < n; i++)
    {
        scanf("%lld", x+i);
        a[i] = x[i] - x[i-1];
    }
    getPrefix();
    return 0;
}