Cod sursa(job #741067)

Utilizator ChallengeMurtaza Alexandru Challenge Data 25 aprilie 2012 12:33:22
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>

using namespace std;

const char InFile[]="reguli.in";
const char OutFile[]="reguli.out";
const int MaxN=500111;

ifstream fin(InFile);
ofstream fout(OutFile);

long long N,x,y,V[MaxN];
int pi[MaxN],k;

int main()
{
	fin>>N>>x;
	for(register int i=1;i<N;++i)
	{
		y=x;
		fin>>x;
		V[i]=x-y;
	}
	fin.close();
	
	k=0;
	pi[1]=0;
	for(register int i=2;i<N;++i)
	{
		while(k>0 && V[k+1]!=V[i])
		{
			k=pi[k];
		}
		if(V[k+1]==V[i])
		{
			++k;
		}
		pi[i]=k;
	}
	
	
	fout<<N-pi[N-1]-1<<"\n";
	for(register int i=1;i<=N-pi[N-1]-1;++i)
	{
		fout<<V[i]<<"\n";
	}
	fout.close();
	return 0;
}