Cod sursa(job #18607)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 18 februarie 2007 12:46:45
Problema Reguli Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.06 kb
# include <stdio.h>

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

# define  maxn  500002

# define  myint long long


myint a[maxn], p[maxn], n;
myint sol;

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

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;
	}
}

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;
}