Cod sursa(job #163104)

Utilizator marinaMarina Horlescu marina Data 21 martie 2008 13:39:13
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
//Reguli  - infoarena - Preoni 2007 Runda 2
#include <stdio.h>
#define INPUT "reguli.in"
#define OUTPUT "reguli.out"
#define NMAX 500001

int N;
int A[NMAX];

int T[NMAX];

void prefix()
{
	int i, k = 0;
	T[1] = 0;
	for(i = 2; i <= N; ++i)
	{
		while((k>0) && A[i] != A[k+1])
			k = T[k];
		if(A[i] == A[k+1]) ++k;
		T[i] = k;
	}
}
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d", &N);
	int x, y, i;
	scanf("%d", &x);
	for(i = 2; i <= N; ++i)
	{
		scanf("%d", &y);
		A[i-1] = y-x;
		x = y;
	}
	--N;
	
	prefix();
	
	int l;
	int ok =  0;
	for(l = 1; l <= N && !ok; ++l)
	{
		int n = N - N%l;
		ok = 1;
		if(!T[n]) ok = 0;
		if(ok && n % (n - T[n]) != 0) ok = 0;
		if(ok && n - T[n] != l) ok = 0;
		int j;
		for(j = n+1; j <= N && ok; ++j)
			if(A[j] != A[j-n]) ok = 0;
	}
	
	printf("%d\n", --l);
	for(i = 1; i <= l; ++i)
		printf("%d\n", A[i]);
	return 0;
}