Cod sursa(job #18178)

Utilizator TheCreeepIonita Andrei Lucian TheCreeep Data 18 februarie 2007 10:23:45
Problema Reguli Scor 30
Compilator c Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.48 kb
#include <stdio.h>
FILE *f;
long long x[500001];
int y[500001],i,p,n;
int main (void)
{
	f=fopen("reguli.in","r");
	fscanf(f,"%d",&n);
	for(i=0;i<n;i++) fscanf(f,"%d",&x[i]);
	for(i=n-1;i>=1;i--) x[i]=x[i]-x[i-1];
	fclose(f);
	
	p=0;
	for(i=2;i<n;i++)
	{
		if (x[i]==x[p+1]) y[i]=++p;
		else
		{
			while (p!=0 && x[p+1]!=x[i]) p=y[p];
			if (p!=0) y[i]=++p;
		}
	}

	f=fopen("reguli.out","w");
	x[0]=n-y[n-1]-1;
	for(i=0;i<=n-y[n-1]-1;i++)
	fprintf(f,"%d\n",x[i]);
	fclose(f);
	return 0;
}