Cod sursa(job #91930)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 13 octombrie 2007 19:52:55
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#define vv 500002

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

void citire()
{
	freopen("reguli.in","r",stdin);
	scanf("%d",&n);
	for (int i=0; i<n; i++)
		scanf("%d",&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];
	}
}

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

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