Cod sursa(job #304883)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 15 aprilie 2009 15:52:24
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#define NM 500010

long long x[NM],d[NM];
int n;
int u[NM];

void urm(){
int k,q;
k=0;
u[1]=0;
for(q=2;q<n;++q){
	while(k&&d[k+1]!=d[q]) k=u[k];
	if(d[k+1]==d[q]) k++;
	u[q]=k;
	}
}

int main(){
freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
int i,j;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%lld",&x[i]);
for(i=1;i<n;++i) d[i]=x[i]-x[i-1];
urm();
int l,c,r,ok,c1,c2,c3;
l=n;d[n]=x[n-1];
n--;
for(i=1;i<=n;++i){
	r=(n)%i,c=(n)/i;
	c1=u[n-r]>0;
	c2=(n-r)%(n-r-u[n-r])==0;
	c3=(n-r)/(n-r-u[n-r])==c;
	ok=1;
	for(j=1;j<=r;++j)
		if(d[j]!=d[n-r+j]) {ok=0;break;}
	if(ok&&c1&&c2&&c3) {l=i;break;}
	}
printf("%d\n",l);
for(i=1;i<=l;++i) printf("%lld\n",d[i]);
return 0;
}