Cod sursa(job #18914)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 18 februarie 2007 14:53:18
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

const int NMAX = 524288;

int N, sol;
long long V[NMAX];
int pi[NMAX];

void read() {
	FILE *fin = fopen("reguli.in", "rt");
	long long last, current;
	int i;

	fscanf(fin, " %d", &N);

	fscanf(fin, " %lld", &last);
	--N;

	for (i = 0; i < N; ++i) {
		fscanf(fin, " %lld", &current);

		V[i] = current - last;
		last = current;
	}

	fclose(fin);
}

void chimp() {
	int i, j;

	for (j = 0, i = 2; i <= N; ++i) {

		while (j > 0 && V[j] != V[i - 1]) j = pi[j];

		if (V[j] == V[i - 1]) ++j;

		pi[i] = j;
	}

//	sol = N - pi[N];

	for (i = 1; i <= N && sol == 0; ++i) {

		for (j = i; j <= N && pi[j] + i == j; j += i);

		if (j > N) {
			if (j < N + i) {
				if (pi[N] >= i - (j - N))
					sol = i;
			} else sol = i;
		}
	}
}

void write() {
	FILE *fout = fopen("reguli.out", "wt");
	int i;

	fprintf(fout, "%d\n", sol);
	for (i = 0; i < sol; ++i)
		fprintf(fout, "%lld\n", V[i]);

	fclose(fout);
}

int main() {

	read();

	chimp();

	write();

	return 0;
}