Cod sursa(job #173837)

Utilizator plastikDan George Filimon plastik Data 8 aprilie 2008 10:15:26
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
// Reguli, Infoarena
// http://infoarena.ro/problema/reguli

#include <cstdio>
#include <cstring>

const int NMAX = 500005;

long long X[NMAX], n;
long long Dif[NMAX];
int Pi[NMAX];

void KMPPrefix() {
	int i, k;
	Pi[1] = 0;
	for (i = 2, k = 0; i <= n - 1; ++ i) {
		while (k > 0 && Dif[i] != Dif[k + 1])
			k = Pi[k];
		if (Dif[i] == Dif[k + 1])
			++ k;
		Pi[i] = k;
	}
}

int main() {
	
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	
	scanf("%lld", &n);
	int i;
	for (i = 0; i < n; ++ i)
		scanf("%lld", &X[i]);
	
	for (i = 1; i <= n - 1; ++ i)
		Dif[i] = X[i] - X[i - 1];
	
	KMPPrefix();
	/*for (i = 1; i <= n - 1; ++ i)
		printf("%d ", Pi[i]);*/
	
	long long ans = n - 1 - Pi[n - 1];
	printf("%lld\n", ans);
	for (i = 1; i <= ans; ++ i)
		printf("%lld\n", Dif[i]);
	
	return 0;
}