Cod sursa(job #145196)

Utilizator ProtomanAndrei Purice Protoman Data 28 februarie 2008 16:17:47
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>   
#define mx 500010    
long long i,n;   
long pi[mx];
long a[mx],x[mx];   
  
void prefix()   
{   
    long long p,i;   
    pi[1]=0;   
    p=0;   
    for (i=2; i<=n; i++)   
    {   
        while (p>0 && x[i]!=x[p+1])   
            p=pi[p];   
        if (x[i]==x[p+1])   
            p++;   
        pi[i]=p;   
    }   
}   
  
int main()   
{   
    freopen("reguli.in","r",stdin);   
    freopen("reguli.out","w",stdout);   
    scanf("%lld",&n);   
    for (i=0; i<n; i++)   
        scanf("%lld",&a[i]);   
    n--;   
    for (i=1; i<=n; i++)   
        x[i]=a[i]-a[i-1];   
    prefix();   
    printf("%lld\n",n-pi[n]);   
    for (i=1; i<=n-pi[n]; i++)   
        printf("%lld\n",x[i]);   
    fclose(stdin);   
    fclose(stdout);   
    return 0;   
}