Cod sursa(job #18462)

Utilizator TYTUSVlad Saveluc TYTUS Data 18 februarie 2007 12:18:16
Problema Reguli Scor 80
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.3 kb
#include <cstdio>
using namespace std;

const int NMAX = 1000001;
typedef long long ll;
ll v[NMAX];
int pi[NMAX], sh[NMAX];

int main() {
	FILE *fin = fopen ("reguli.in", "r");
	FILE *fout = fopen ("reguli.out", "w");
	int n, i;
	fscanf (fin, "%d\n%lld\n", &n, &v[0]);
	for (i = 1; i < n; ++i) {
		char s[30];
		fgets(s, 30, fin);
		int j, sigm;
		ll x;
		if (s[0] == '-') {
			x = s[1] - '0';
			j = 2;
			sigm = 1;
		} else {
			x = s[0] - '0';
			j = 1;
			sigm = 0;
		}
		for (; s[j] >= '0' && s[j] <= '9'; ++j) {
			x = x * 10 + (ll)s[j] - '0';
		}
		if (sigm) {
			v[i] = -x;
		} else {
			v[i] = x;
		}
	}
	for (i = n - 1; i > 0; --i) {
		v[i] -= v[i - 1];
	}/*
	for (i = 1; i < n; ++i) {
		printf ("%lld\n", v[i]);
	}*/
	int k = 0, ret = 2 * NMAX;
	pi[1] = 0;
	sh[1] = 1;
	for (i = 2; i <= 2 * (n - 1); ++i) {
		while (k > 0 && !(v[k + 1] == v[i] || i >= n - 1)) {
			k = pi[k];
		}
		if (v[k + 1] == v[i] || i >= n - 1) {
			k++;
		}
		pi[i] = k;
		if (pi[i] == 0) {
			sh[i] = i;
		} else {
			if (sh[i - pi[i]] <= pi[i]) {
				sh[i] = sh[i - pi[i]];
			} else {
				sh[i] = i;
			}
		}
// 		printf ("pi = %d Sh[%d] = %d\n", pi[i], i, sh[i]);
		if (i >= n - 1 && sh[i] < ret) {
			ret = sh[i];
		}
	}
	fprintf (fout, "%d\n", ret);
	for (i = 1; i <= ret; ++i) {
		fprintf (fout, "%lld\n", v[i]);
	}
	fclose(fout);
	return 0;
}