Cod sursa(job #154638)

Utilizator filipbFilip Cristian Buruiana filipb Data 11 martie 2008 12:40:27
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <stdio.h>

#define NMax 500005
#define ll long long

int N, pi[NMax];
ll v[NMax];

int main(void)
{
	int i, q = 0;
	ll ant, x;
	
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);

	scanf("%d", &N);
	scanf("%lld", &ant);
	for (i = 1; i < N; ++i)
	{
		scanf("%lld", &x);
		v[i] = x-ant;
		ant = x;
	}
	--N;
	
	for (i = 2; i <= N; ++i)
	{
		while (q > 0 && v[q+1] != v[i])
			q = pi[q];
		if (v[q+1] == v[i])
			++q;
		pi[i] = q;
	}

	N -= pi[N];
	printf("%d\n", N);
	for (i = 1; i <= N; ++i)
		printf("%lld\n", v[i]);
	
	return 0;
	
}