Cod sursa(job #18763)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 18 februarie 2007 13:58:55
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>

#define maxn 500010
#define ll long long 

int n,l;
ll a[maxn];
int p[maxn];

void prefix()
{
     int i,x=0;
     
     p[0]=0;
     for (i=2;i<=n;i++)
     {
		 while ((x>0) && (a[x+1]!=a[i])) x=p[i];
         if (a[x+1]==a[i]) x++;
         p[i]=x;         
     }
}

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    
    int i,poz;
    scanf("%d ",&n);
    
    for (i=1;i<=n;i++) scanf("%lld",&a[i]);
    
    for (i=1;i<n;i++) a[i]=a[i+1]-a[i];
    n--;
    
    prefix();
    
    l=n-p[n];
      
    printf("%d\n",l);
    for (i=1;i<=l;i++) printf("%lld\n",a[i]);
    
    return 0;
}