Cod sursa(job #309925)

Utilizator irene_mFMI Irina Iancu irene_m Data 1 mai 2009 14:07:33
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream.h>
#define MaxN 500005

long long n,d[MaxN],pi[MaxN],ok[MaxN],L,x;

void cit()
{
	int i,a,b;
	ifstream fin("reguli.in");
	fin>>n>>a;
	for(i=1;i<n;i++)
	{
		fin>>b;
		d[i]=b-a;
		a=b;
	}
}		

void prefix()
{
	int k=0,i;
	for(i=2;i<n;i++)
	{
		while(k && d[k+1]!=d[i])
			k=pi[k];
		if(d[k+1]==d[i])
			k++;
		pi[i]=k;
		if(k && i%(i-k)==0)  
            x=k;
	}
}

void OK()
{
	int k;
	n--;
	k=pi[n];
	while(!ok[k])
	{
		ok[k]=1;
		k=pi[k];
	}
}

void perioada()
{
	int i,r,c;
	for(i=1;i<=n;i++)
	{
		r=n%i;
		c=n/i;
		if(pi[n-r] && (n-r)%(n-r-pi[n-r])==0 && (n-r)/(n-r-pi[n-r])==c && ok[r])
			L=i;
	}
}

void afis()
{
	int i;
	ofstream fout("reguli.out");
	/*for(i=1;i<=n;i++)
		fout<<d[i]<<" ";
	fout<<'\n';*/
	if(L==0)
		L=n;
	fout<<L<<'\n';
	for(i=1;i<=L;i++)
		fout<<d[i]<<'\n';
	fout.close();
}

int main()
{
	cit();
	prefix();
	OK();
	perioada();
	afis();
	return 0;
}