Cod sursa(job #18752)

Utilizator wefgefAndrei Grigorean wefgef Data 18 februarie 2007 13:55:12
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>

#define Nmax 500005

int n, pref[Nmax];
long long v[Nmax];

void readdata()
{
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	
	int i;
	long long val, nou;
	
	scanf("%d", &n);
	--n;
	scanf("%lld", &val);
	for (i = 1; i <= n; ++i)
	{
		scanf("%lld", &nou);
		v[i] = nou-val;
		val = nou;
	}
}

void solve()
{
	int k, i, j;
	
	pref[1] = 0;
	k = 0;
	for (i = 2; i <= n; ++i)
	{
		while (k && v[k+1] != v[i]) k = pref[k];
		if (v[k+1] == v[i]) ++k;
		pref[i] = k;
	}
	i = n-pref[n];
	printf("%d\n", i);
	for (j = 1; j <= i; ++j)
		printf("%lld\n", v[j]);
}

int main()
{
	readdata();
	solve();
	return 0;
}