Cod sursa(job #907110)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 7 martie 2013 16:59:55
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream>
using namespace std;
int n,L,pi[500100];
long long X[500100],v[500100];

inline void Citire()
{
	int i;
	ifstream fin("reguli.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>X[i];
	fin.close();
}

inline void Rezolvare()
{
	int i,k=0;
	for(i=1;i<n;i++)
		v[i]=X[i+1]-X[i];
	n--;
	pi[1]=0;
	for(i=2;i<=n;i++)
	{
		while(k && v[k+1]!=v[i]) k=pi[k];
		if(v[k+1]==v[i]) k++;
		pi[i]=k;
	}
	L=n-pi[n];
}

inline void Afisare()
{
	int i;
	ofstream fout("reguli.out");
	fout<<L<<"\n";
	for(i=1;i<=L;i++)
		fout<<v[i]<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}