Cod sursa(job #356093)

Utilizator marinMari n marin Data 13 octombrie 2009 15:14:09
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <string.h>
#define DIM 500101

long long A[DIM];
int P[DIM];
int OK[DIM];

int N, i, k, R, C, L, X;

int main(){
	FILE *f = fopen("reguli.in","r");

	fscanf(f,"%d",&N);
	for (i=1;i<=N;i++)
		fscanf(f,"%lld",&A[i]);
	fclose(f);
	
	for (i=1;i<N;i++)
		A[i] -= A[i+1];
	
	N--;

	P[1] = 0;
	for (i=2, k=0;i<=N;i++) {
		while (A[i] != A[k+1] && k>0)
			k = P[k];
		if (A[i] == A[k+1]) {
			k++;
			P[i] = k;
		}/* else
			P[i] = 0;*/
	}
	
	k=N;
	while (k) {
		OK[P[k]] = 1;
		k=P[k];
	}

	for (L=1;L<=N;L++) {
		R = N%L;
		C = N/L;
		X = N-R;
		if ((P[X]>0) && (X%(X-P[X]) == 0) && (X/(X-P[X]) == C) && OK[R]){
			break;
		}
	}

	
	
	FILE *g = fopen("reguli.out","w");
	fprintf(g,"%d\n",L);
	for (i = 1;i<=L;i++)
		fprintf(g,"%lld\n",-A[i]);
	fclose(g);
	
	return 0;
}