Cod sursa(job #733066)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 11 aprilie 2012 13:25:53
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>

int N, Pi[500005];
long long A[500005];

void cit ()
{
	long long aa, bb;
	scanf ("%d%lld", &N, &aa);
	for (int i = 1; i < N; i++)
	{
		scanf ("%lld", &bb);
		A[i] = bb - aa;
		aa = bb;
	}
}

void pre ()
{
	Pi[1] = 0;
	for (int i = 2, j = 0; i < N; i++)
	{
		while (j != 0 && A[i] != A[j+1])
			j = Pi[j];
		if (A[i] == A[j+1])
			j++;
		Pi[i] = j;
	}
}

void afi ()
{
	A[0] = N-1 - Pi[N-1];
	for (int i = 0; i <= A[0]; i++)
		printf ("%lld\n", A[i]);	
}

int main ()
{
	freopen ("reguli.in", "r",stdin);
	freopen ("reguli.out", "w",stdout);
	
	cit ();
	pre ();
	afi ();
	
	return 0;
}