Cod sursa(job #177329)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 12 aprilie 2008 18:03:45
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <math.h>

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

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("%lld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%lld", &nr);
		if (i > 1) {
			A[i - 1] = nr - nr1;
		}
		nr1 = nr;
	}
	make_prefix();
	--n;
	printf("%lld\n", n - p[n]);
	for (i = 1; i <= n - p[n]; ++i) {
		printf("%lld\n", A[i]);
	}
	return 0;
}