Cod sursa(job #48032)

Utilizator amadaeusLucian Boca amadaeus Data 4 aprilie 2007 12:48:13
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

using namespace std;
#define NX 500010

long long v[ NX ];
int pi[ NX ];
bool ok[ NX ];
int N, best;

void cit() {
	long long x, y;
	int i;
	
	scanf( "%d", &N );
	for( i = 0; i < N; i++ ) {
		scanf( "%lld", &x );
		v[i] = x - y;
		y = x;
	}
}

void calc_pi() {
	int i, k;
	for( pi[0] = k = -1, i = 1; i < N; pi[i++] = ++k )
		while( k >= 0 && v[k+1] != v[i] )
			k = pi[k];
}

void calc_ok() {
	int k;
	
	for( k = pi[ N-1 ]; k; k = pi[k] )
		ok[ k ] = true;
}

inline
void umin( int& x, int y ) {
	if( x > y )
		x = y;
}

void kmp() {
	int k;
	
	best = N - 1;
	for( k = 1; k < N; k++ )
		if( (pi[k] > 0) && (k % (k - pi[k]) == 0) && ok[ N - 1 - k + pi[k] ] )
			umin( best, k - pi[k] );
}

void rez() {
	calc_pi();
	calc_ok();
	kmp();
}

void scr() {
	int i;

	printf( "%d\n", best );
	for( i = 1; i <= best; i++ )
		printf( "%lld\n", v[i] );
/*
	for( i = 1; i < N; i++ )
		printf( "%lld ", v[i] );
	printf( "\n" );

	for( i = 1; i < N; i++ )
		ok[i] ? printf( "1 " ) : printf( "0 " );
*/
}

int main() {
	freopen( "reguli.in", "r", stdin );
	freopen( "reguli.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}