Cod sursa(job #195692)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 20 iunie 2008 21:48:06
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>   
  
#define NMAX 30000

long long x[NMAX],a[NMAX];
long long i,k,n,s,PI[NMAX];
  
int main()   
{   
freopen("reguli.in","rt",stdin);
freopen("reguli.out","wt",stdout);
scanf("%lld",&n);
for (i=0;i<n;i++)
scanf("%lld",&x[i]);
for (i=1;i<n;i++)
a[i]=x[i]-x[i-1];
//functia prefix
PI[1]=k=0;
for (i=2;i<n;i++)
    {
     while (k>0 && a[k+1]!=a[i])
	    k=PI[k];
	   if (a[k+1]==a[i])
	    k++;
    PI[i]=k;
    }
k=n-1-PI[n-1];
s=1;
for (i=k+1;i<n;i++)
    if (a[i]!=a[i-k])
	{s=0;
	 break;
        }   
if (!s) k=n-1;
printf("%lld\n",k);
for (i=1;i<=k;i++)
printf("%lld\n",a[i]);
return 0;}