Cod sursa(job #18264)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 18 februarie 2007 11:06:23
Problema Reguli Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.3 kb
//# define DEBUG 1

# include <stdio.h>
//# include <conio.h>

# define  _fin  "reguli.in"
# define  _fout "reguli.out"

# define  maxn  500002

# define  myint long// long


myint a[maxn], p[maxn], n;
myint sol;	// lungimea secventei

void readf()
{
	freopen(_fin, "r", stdin);
	myint i, first, aux;
	
	scanf("%lld%lld", &n, &first);
	
	for (i=1; i<n; i++)
	{
		scanf("%lld", &aux);
		a[i] = aux-first;
		first = aux;
	}
	
//	if ( DEBUG )
//	for (i=1; i<n; i++)
//	    printf("%d ", a[i]);
}

void calculp()
{
	myint k=0, q;
	
	for (q=2; q<n; q++)
	{
		while ( k > 0 && a[k+1] != a[q] ) k = p[k];
		if ( a[k+1] == a[q] ) ++k;
		p[q] = k;
	}
	
/*	if ( DEBUG )
	{
		for (int i=1; i<n; i++)
			printf("%lld ", p[i]);
		getch();
	}*/
}

void solve()
{
	calculp();

	int i, k, found=0;	// found

	for (i=2; i<n; i++)
	{
		if ( !found )
		{
			if ( p[i]==1 )	// posibil inceput de perioada
				found = 1, k=i-1;
		}
		
		else
		{
			if ( p[i] % k != i % k || p[i] != p[i-1]+1 )
				found = 0;
		}
	}
	
	if ( found )
		sol = k;
	
	else
		sol = n-1;
}

void writef()
{
	freopen(_fout, "w", stdout);
	int i;

	for (printf("%lld\n", sol), i=1; i<=sol; i++)
		 printf("%lld\n", a[i]);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}