Cod sursa(job #150019)

Utilizator scvalexAlexandru Scvortov scvalex Data 6 martie 2008 15:13:07
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <cstdio>
#include <fstream>

using namespace std;

int N,
	D[500000],
	pi[500000];

int main(int argc, char *argv[]) {
	FILE *fi = fopen("reguli.in", "r");
	fscanf(fi, "%d", &N);
	int last,
		now;
	fscanf(fi, "%d", &last);
	for (int i(1); i < N; ++i) {
		fscanf(fi, "%d", &now);
		D[i] = now - last;
		last = now;
	}
	fclose(fi);

	/*for (int i(0); i < N; ++i)
		cout << i << " ";
	cout << endl;
	for (int i(0); i < N; ++i)
		cout << D[i] << " ";
	cout << endl;*/

	// calculez pi
	pi[1] = 0;
	int k = 0;
	for (int i(2); i < N; ++i) {
		while ((k > 0) && (D[k + 1] != D[i]))
			k = pi[k];

		if (D[k + 1] == D[i])
			++k;

		pi[i] = k;
	}

	/*for (int i(0); i < N; ++i)
		cout << pi[i] << " ";
	cout << endl;*/

	--N;
	int L;
	for (L = N; L >= 1; --L) {
		//cout << L << " " << pi[L] << endl;
		int r = N % L,
			c = N / L;

		int aux = N - r;
		if (pi[aux] == 0)
			continue;

		//cout << "pi[L] != 0" << endl;

		if (aux % (aux - pi[aux]) != 0)
			continue;

		//cout << "restul este bun" << endl;

		if (N / (aux - pi[aux]) != c)
			continue;

		//cout << "catule este bun" << endl;

		for (int i = N - r; i <= N; ++i)
			if (D[i] != D[i - N + r])
				continue;

		//cout << "sfarsitul se potriveste" << endl;

		break;
	}

	//cout << L << endl;

	if (L == 0)
		L = N;

	FILE *fo = fopen("reguli.out", "w");
	fprintf(fo, "%d\n", L);
	for (int i(1); i <= L; ++i)
		fprintf(fo, "%d\n", D[i]);
	fclose(fo);

	return 0;
}