Cod sursa(job #338568)

Utilizator ilincaSorescu Ilinca ilinca Data 6 august 2009 01:59:13
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h> 

#define nmax 500005

int n, pi [nmax];
bool ok [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;
	}
}

void form_ok ()
{
	int x=pi [n];
	while (x != 0) 
	{
		ok [x]=true;
		x=pi [x];
	}
}

int rez ()
{
	int i, q=0, r, c;
	pi [1]=0;
	--n;
	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 ); 	
	}	
	form_ok ();
	if (pi [n] == n-1) 
		return 1;
	for (i=2; i <= n; ++i)
	{
		r=n%i;
		c=n/i;
		//if (!pi [n-r]) continue;
		if (c > 1)
		{
			if (!pi [n-r]) continue;	
			if ((n-r)%(n-r-pi [n-r])) continue;
			if ((n-r)/(n-r-pi [n-r]) != c) continue;
		}
		if (!ok [r]) continue;
		return i;
	}	
	return n;
}

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;
}