Cod sursa(job #214194)

Utilizator Mishu91Andrei Misarca Mishu91 Data 13 octombrie 2008 11:19:33
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>

#define MAX_N 500005

long long 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()
{
    long long 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;
    if(pi[N-1])
        for(i = N - 1; i > 1; --i)
            if((pi[i] - pi[i-1] != 1 && pi[i] == 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();
}