Cod sursa(job #22612)

Utilizator damaDamaschin Mihai dama Data 26 februarie 2007 22:32:10
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>

long long n, v[500001], pi[500001], k, sol;

int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	
	long long a, b, i;
	
	scanf("%lld", &n);
	for(i = 0; i < n; ++i)
	{
		scanf("%lld", &v[i]);
	}
	for(i = n - 1; i > 0; --i)
	{
		v[i] -= v[i - 1];
	}
	
	
	for(i = 2; i < n; ++i)
	{
		while(k > 0 && v[k + 1] != v[i])
		{
			k = pi[k];
		}
		if(v[k + 1] == v[i])
		{
			++k;
		}
		pi[i] = k;
	}
	
	sol = n - 1 - pi[n - 1];
	
	printf("%d\n",sol);
	
	for(i = 1; i <= sol; ++i)
	{
		printf("%d\n", v[i]);	
	}
	
	
	return 0;
}