Cod sursa(job #145119)

Utilizator ProtomanAndrei Purice Protoman Data 28 februarie 2008 14:11:25
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#define mx 500010 
long long i,n;
long long pi[mx],a[mx],x[mx];

void prefix()
{
	long long p,i;
	pi[1]=0;
	p=0;
	for (i=2; i<=n; i++)
	{
		while (p>0 && x[i]!=x[p+1])
			p=pi[p];
		if (x[i]==x[p+1])
			p++;
		pi[i]=p;
	}
}

int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf("%ld",&n);
	for (i=0; i<n; i++)
		scanf("%lld",&a[i]);
	n--;
	for (i=1; i<=n; i++)
		x[i]=a[i]-a[i-1];
	prefix();
	printf("%lld\n",n-pi[n]);
	for (i=1; i<=n-pi[n]; i++)
		printf("%lld\n",x[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}