Cod sursa(job #91935)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 13 octombrie 2007 20:00:56
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#define vv 500002

long n;
long long x[vv],w[vv],p[vv],max;//,q[vv];

void citire()
{
	freopen("reguli.in","r",stdin);
	scanf("%ld",&n);
	for (int i=0; i<n; i++)
		scanf("%lld",&x[i]);
	fclose(stdin);
}

void prec()
{
	int k=0;
	p[1]=0;
	w[1]=x[1]-x[0];
//	q[0]=1;
//	q[1]=w[1];
	for (int i=2; i<n; i++)
	{
		w[i]=x[i]-x[i-1];
		while (k>0 && w[k+1]!=w[i])
			k=p[k];
		if (w[k+1]==w[i])
			++k;
		p[i]=k;
		if (p[i]==0)
			//q[++q[0]]=w[i];
			max=i;
	}
}

void afisare()
{
	freopen("reguli.out","w",stdout);
	//for (int i=0; i<=q[0]; i++)
	//	printf("%lld\n",q[i]);
	printf("%lld\n",max);
	for (int i=1; i<=max; i++)
		printf("%lld\n",w[i]);
	fclose(stdout);
}

int main()
{
	citire();
	prec();
	afisare();
	return 0;
}