Cod sursa(job #19724)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 19 februarie 2007 21:23:32
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <stdio.h>

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

# define  maxn  500005

# 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, r, c;	// found
	--n;
	
	for (i=1; i<n; i++)
	{
		r = n % i;
		c = n / i;
		
		if ( p[n-r] > 0 && (n-r) % (n-r-p[n-r]) == 0 && (n-r) / (n-r-p[n-r])==c )
		{
			sol = i;
			return;
		}
	}

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