Cod sursa(job #29202)

Utilizator pocaituDavid si Goliat pocaitu Data 8 martie 2007 19:13:23
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#define nmax 500003

long long  d[nmax],n,Urm[nmax];
void Urmatorul()
{long long k=0,x;
 Urm[1]=0;
 for(x=2;x<=n;x++)
  {while(k>0&&d[k+1]!=d[x]) k=Urm[k];
	if(d[k+1]==d[x]) k++;
	Urm[x]=k;

	}
 }

int main()
{long long  i,x,x1=0,l,r,c;
freopen("reguli.in","r",stdin);
 scanf("%lld",&n);
 scanf("%lld",&x1);
 for(i=1;i<n;i++)
  {scanf("%lld",&x);
   d[i]=x-x1;
   x1=x;
   }
 n--;
 Urmatorul();
 for(l=1;l<=n;l++)
  {c=n/l;
   r=n%l;
   if(Urm[n-r]>0&&!((n-r)%(n-r-Urm[n-r]))&&(n-r)/(n-r-Urm[n-r])==c&&(Urm[n]==n-l))
	 {freopen("reguli.out","w",stdout);
	  printf("%lld\n",l);
	   for(i=1;i<=l;i++)
		printf("%lld\n",d[i]);
	   fclose(stdout);
	 return 0;
	 }

 }
 freopen("reguli.out","w",stdout);
	  printf("%lld\n",n-1);
	   for(i=1;i<=n-1;i++)
		printf("%lld\n",d[i]);
	   fclose(stdout);

 return 0;
 }