Cod sursa(job #475033)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 5 august 2010 19:07:31
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

#define file_in "reguli.in"
#define file_out "reguli.out"

#define nmax 500010

long long a[nmax];
long long sir[nmax];
int n;
int pi[nmax];

void citire()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=0;i<n;++i)
		 scanf("%lld", &sir[i]);
}

void solve()
{
	int i,k,ok,l;
	for (i=1;i<n;++i)
		 a[i]=sir[i]-sir[i-1];
	
	//baga prefix
	k=0;
	pi[1]=0;
	
	for (i=2;i<n;++i)
	{
		while(a[k+1]!=a[i] && k>0) k=pi[k];
		if (a[k+1]==a[i]) k++;
		pi[i]=k;
	}
	l=n-1-pi[n-1];
	//printf("%d\n", l);
	ok=1;
	for (i=l+1;i<n && ok;++i)
		 if (a[i]!=a[i-l]) ok=0;
	if (!ok)
		l=n-1;
	printf("%d\n", l);
	for (i=1;i<=l;++i)
		 printf("%lld\n", a[i]);
	
}
			 

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	
	return 0;
	
}