Cod sursa(job #338382)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 5 august 2009 17:10:05
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <stdio.h>
#define Nmax 500005
#define ll long long

ll a[Nmax];
long pi[Nmax];
int n,i,per;

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

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

   prefix();

   per=n-1-pi[n-1];
   printf("%d\n",per);
   for(i=1;i<=per;++i) printf("%d\n",a[i]);

   fclose(stdin); fclose(stdout);
   return 0;
}