Cod sursa(job #197272)

Utilizator cristitalauCristian Talau cristitalau Data 3 iulie 2008 01:02:34
Problema Reguli Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#include <string.h>

#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005

int M, pi[NMax];
long long A[NMax];
char ok[NMax];

void make_prefix(void)
{
	int i = 2, q = 0;
	for (  pi[1] = 0; i <= M; pi[i++] = q){
		for ( ; q && A[q+1] != A[i];  q = pi[q]);
		if ( A[q+1] == A[i] ) ++q;
	}
}

int main(void)
{
	int i, q = 0, l = 0;
	
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	

	scanf("%d", &M);
	for( i = 1; i< M+1; i++){
		scanf("%d", &A[i]);
		if(i) A[i-1] = A[i] - A[i-1];
	}

	memset(ok, 0, M);
	make_prefix();

	for(q = M-1;  q!=0; ok[q] = 1, q = pi[q]); 

	int r,c,m, p = M;
	for( l = M-1; l >  0; --l){
		r = (M-1) % l, c = (M-1) / l, m = (M-1) - r;
		if( pi[ m ]  && (m % (m-pi[m])) == 0 && m/(m-pi[m]) ==c && ok[r] )
			p = l;
	}

	printf("%d\n",  p) ;
	for(i = 0; i < p; i++)
		printf("%d\n", A[i+1]);

	return 0;
}