Cod sursa(job #148625)

Utilizator scvalexAlexandru Scvortov scvalex Data 4 martie 2008 16:51:35
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <fstream>

using namespace std;

int N,
	K,
	D[500000];

int gaseste_prima_aparitie_a_lui(int x) {
	for (int i(0); i < K; ++i)
		if (D[i] == x)
			return i + 1;
	return 0;
}

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 - 1] = now - last;
		last = now;
	}
	fclose(fi);
	--N;

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

	K = 1;
	int cur(0);
	for (int i(1); i < N; ++i) {
		if (D[i] == D[cur]) {
			cur = (cur + 1) % K;
		} else {
			int d = gaseste_prima_aparitie_a_lui(D[i]);
			bool match(true);
			for (int j(0); j < d; ++j)
				if (D[j] != D[i + 1 - d + j])
					match = false;
			if (match) {
				cur = d; 
				K = i + 1 - d;
			} else {
				cur = 0;
				K = i + 1; 
			}
		}
	}

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

	return 0;
}