Cod sursa(job #732951)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 11 aprilie 2012 11:30:52
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<stdio.h>

#define maxn 500005

FILE*f=fopen("reguli.in","r");
FILE*g=fopen("reguli.out","w");

int n;
int pi[maxn];
long long A[maxn];

int main () {
	
	fscanf(f,"%d",&n);
	
	long long x,y;
	fscanf(f,"%lld",&y);
	for ( int i = 2 ; i <= n ; ++i ){
		fscanf(f,"%lld",&x);
		A[i-1] = x - y;
		y = x;
	}
	--n;
	
	int k = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		while ( k > 0 && A[k+1] != A[i] ){
			k = pi[k];
		}
		
		if ( A[k+1] == A[i] ){
			++k;
			pi[i] = k;
		}
	}
	
	fprintf(g,"%d\n",n-pi[n]);
	for ( int i = 1 ; i <= n-pi[n] ; ++i ){
		fprintf(g,"%lld\n",A[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}