Cod sursa(job #309629)

Utilizator irene_mFMI Irina Iancu irene_m Data 30 aprilie 2009 19:50:42
Problema Reguli Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <fstream.h>
#define MaxN 500005

int n,y[MaxN],pi[MaxN],x=MaxN;

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

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

void afis()
{
	ofstream fout("reguli.out");
	int i;
	fout<<x<<'\n';
	for(i=1;i<=x;i++)
		fout<<y[i]<<'\n';
	fout.close();
}

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