Cod sursa(job #177327)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 12 aprilie 2008 17:55:36
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>
#include <math.h>

long n, nr, nr1, i, A[500001], p[500001];

void make_prefix() {
	long i, q = 0;

	for (i = 2, p[1] = 0; i <= n + 1; ++i) 	{
		while (q && A[q + 1] != A[i]) {
			q = p[q];
		}
		if (A[q + 1] == A[i]) {
			++q;
		}
		p[i] = q;
	}
}

int main() {
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &nr);
		if (i > 1) {
			A[i - 1] = nr - nr1;
		}
		nr1 = nr;
	}
	make_prefix();
	--n;
	printf("%ld\n", n - p[n]);
	for (i = 1; i <= n - p[n]; ++i) {
		printf("%ld\n", A[i]);
	}
	return 0;
}