Cod sursa(job #479444)

Utilizator Programmer01Mierla Laurentiu Marian Programmer01 Data 24 august 2010 02:29:13
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#include<string.h>

long long *a, *p,  n;

void prefix(){
	long long k = -1;
	p[0] = -1;
	for(long long i=1; i<n; i++) {
		while(k >= 0 && a[i] != a[k+1])
			k = p[k];
		if(a[k+1] == a[i]) ++k;
		p[i] = k;
	}
}

void solve(){
	for(long long i=1; i<n; i++)
		a[i-1] = a[i] - a[i-1];
	--n;
	
	prefix();
	
	long long ant = p[n-1]; 
	if(ant == 0) {
		--n;
		return;
	}
	if(ant == -1) return;
	
	for(--n; --n >=0 && p[n] < ant && p[n] != 0; ant = p[n]);
}

void read(){
	FILE *ifile;
	
	ifile = fopen("reguli.in", "r");
	fscanf(ifile, "%I64d", &n);
	
	a = new long long[n];
	p = new long long[n-1];
	for(long i=0; i<n; i++)
		fscanf(ifile, "%I64d", &a[i]);

	fclose(ifile);
}

void write(){
	FILE *ofile;

	ofile = fopen("reguli.out", "w");
	fprintf(ofile, "%I64d\n", n);
	
	for(int i=0; i<n; i++)
		fprintf(ofile, "%I64d\n", a[i]);
	fclose(ofile);
}


int main()
{
	read();
	solve();
	write();
	return 0;
}