Cod sursa(job #783944)

Utilizator adascaluAlexandru Dascalu adascalu Data 4 septembrie 2012 16:15:56
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
#include<vector>
#define MAXN 500000
using namespace std;
vector<long long >dif(MAXN);
int n;
FILE *g=fopen("reguli.out","w");
int kmp(int lg)
{
	vector<long long > a(MAXN),pi(MAXN),match(MAXN);
	int i,k=0,max=0;
	for(i=1;i<=lg;++i)
		a[i]=dif[i];
	pi[1]=0;
	for(i=2;i<=lg;i++)
	{
		while(k && a[i]!=a[k+1])
			k=pi[k];
		if(a[i]==a[k+1])
			k++;
		pi[i]=k;
	}
	k=0;
	for(i=1;i<=n;i++)
	{
		while(k && dif[i]!=a[k+1])
			k=pi[k];
		if(dif[i]==a[k+1])
			++k;
		match[i]=k;
		max=max<k ? k :max;
	}
	//fprintf(g,"\n");
	for(i=1;i<n;i++)
	{
	//	fprintf(g,"%lld\n",match[i]);
		if(!match[i])
			return 0;
	}
	for(i=2;i<n;i++)
	{
		if(match[i]!=match[i-1]+1 && match[i-1]!=max )
			return 0;
		else
			if(match[i-1]==max &&match[i]!=1)
				return 0;
	}
	return 1;
}
int main ()
{
	FILE * f=fopen("reguli.in","r");
	//FILE *g=fopen("reguli.out","w");
	fscanf(f,"%u",&n);
	long long x,y;
	int i;
	fscanf(f,"%lld",&x);
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%lld",&y);
		dif[i]=y-x;
		x=y;
		//fprintf(g,"%lld  ",dif[i]);
	}
	x=0;
	for(i=1;i<n && !x;i++)
		if(kmp(i))
			x=i;
	fprintf(g,"%u\n",x);
	for(i=1;i<=x;i++)
		fprintf(g,"%lld\n",dif[i]);
	return 0;
}