Cod sursa(job #214150)

Utilizator Mishu91Andrei Misarca Mishu91 Data 12 octombrie 2008 22:58:00
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

#define MAX_N 500005

int V[MAX_N], A[MAX_N], pi[MAX_N];
int N;

void citire()
{
    scanf("%d",&N);

    for(int i = 0; i < N; ++i)
        scanf("%d",V+i);

    for(int i = 1; i < N; ++i)
        A[i] = V[i] - V[i-1];
}

void make_prefix()
{
    int i, q = 0;
    for(i = 2, pi[1] = 0; i < N; ++i)
    {
        while(q && A[q+1] != A[i])
            q = pi[q];
        if(A[q+1] == A[i])
            ++q;
        pi[i] = q;
    }
}

void querry()
{
    int i = N-1;
    if(pi[N-1])
        for(i = N - 1; i > 1; --i)
            if(pi[i] - pi[i-1] != 1 || pi[i-1] == 0)
                break;
    printf("%d\n",i-1);
    for(int k = 1; k < i; k++)
        printf("%d\n",A[k]);
}

int main()
{
    freopen("reguli.in","rt",stdin);
    freopen("reguli.out","wt",stdout);

    citire();
    make_prefix();
    querry();
}