Cod sursa(job #594335)

Utilizator drywaterLazar Vlad drywater Data 7 iunie 2011 09:14:25
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
using namespace std;
long long c,r,n,i,k,x,xp,a[500001],pr[500001],ook[500001];
int main(void)
{
	ifstream f("reguli.in");
	ofstream o("reguli.out");
	f>>n;
	f>>xp;
	for (i=1;i<n;i++){f>>x; a[i]=x-xp; xp=x;}
	k=0;
	pr[1]=0;
	for (i=2;i<n;i++)
	{
		while (k>0 && a[k+1]!=a[i]) k=pr[k];
		if (a[k+1]==a[i]) k++;
		pr[i]=k;
	}
	x=pr[n-1];
	while (x)
	{
		ook[x]=1;
		x=pr[x];
	}
	n--;
	for (i=1;i<=n;i++)
	{
		r=n%i;
		c=n/i;
		x=pr[n-r];
		if (x>0 && (n-r)%(n-r-x)==0 && (n-r)/(n-r-x)==c && ook[r]) 
		{o<<i<<'\n'; for (x=1;x<=i;x++) o<<a[x]<<'\n'; break;}
		
		
	}
	if (i>n)
	{
	o<<n<<'\n';
	for (i=1;i<=n;i++) o<<a[i]<<'\n';
	}
	return 0;
}