Cod sursa(job #977812)

Utilizator smaraldaSmaranda Dinu smaralda Data 26 iulie 2013 18:08:43
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<stdio.h>
#define NMAX 500000
long long pi[NMAX+5],dif[NMAX+5];
int main() {
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    long long x,last,n,i,p=0;
    scanf("%lld",&n);
    scanf("%lld",&last);
    for(i=2;i<=n;i++) {
        scanf("%lld",&x);
        dif[i-1]=x-last;
        last=x;
        }
    p=0;
    for(i=2;i<n;i++) {
        while(p && dif[i]!=dif[p+1])
            p=pi[p];
        if(dif[p+1]==dif[i])
            p++;
        pi[i]=p;
        }
    printf("%lld\n",n-1-pi[n-1]);
    for(i=1;i<=n-1-pi[n-1];i++)
        printf("%lld\n",dif[i]);
    return 0;
}