Cod sursa(job #177083)

Utilizator savimSerban Andrei Stan savim Data 12 aprilie 2008 11:13:58
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <stdio.h>
#define maxl 500010

int i,j,x,n;
long long v[maxl],a[maxl];
int pref[maxl];

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%lld",&v[i]);
    
    for (i=2; i<=n; i++)
        a[i-1]=v[i]-v[i-1];
    n--;

    x=0;
    for (i=2; i<=n; i++)
    {
        while (a[i]!=a[x+1] && x) x=pref[x];
        if (a[i]==a[x+1])
        {
           x++;
           pref[i]=x;                 
        }
    }

    printf("%d\n",n-pref[n]);
    for (i=1; i<=n-pref[n]; i++)
        printf("%d\n",a[i]);
    
    return 0;    
}