Cod sursa(job #338339)

Utilizator ilincaSorescu Ilinca ilinca Data 5 august 2009 15:32:39
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h> 

#define nmax 500005

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


void scan ()
{
	int i;
       	long long x, aux;
	scanf ("%d%lld", &n, &aux);
	for (i=1; i < n; ++i)
	{
		scanf ("%lld", &x);
		a [i]=x-aux;
		aux=x;
	}
}

int rez ()
{
	int i, q=0, r=1;
	pi [1]=0;
	for (i=2; i < n; ++i)
	{
		while (q && a [q+1] != a [i])
		       q=pi [q];
		if (a [q+1] == a [i]) 
			++q;
		pi [i]=q;
		//fprintf(stderr, "i=%d q=%d\n",i, q ); 
		if (pi [i] <= pi [i-1]) r=i;
	}	
	return r;
}

void print (int x)
{
	int i;
	printf ("%d\n", x);
	for (i=1; i <= x; ++i) 
		printf ("%lld\n", a [i]);
}

int main ()
{
	freopen ("reguli.in", "r", stdin);
	freopen ("reguli.out", "w", stdout);
	scan ();
	print (rez ());
	return 0;
}