Cod sursa(job #197270)

Utilizator cristitalauCristian Talau cristitalau Data 3 iulie 2008 00:56:24
Problema Reguli Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <string.h>

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

int M, N;
char A[NMax], ok[NMax];
int pi[NMax], pos[1024];

// pi[k] = n => cel mai lung prefix al lui M care este sufix al lui M[1:k] => n<k
//
//  1 2 3 4 5 6 7
//	a a b a a b a _ _ _
// 		  a a b a _ _ _
// pi[7] = 4

// pi[k+1] = 1+ pi[k]  daca M[k+1]= M[ pi[k]+1] ; 
// pi[k+1] = pi

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, n = 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;
}