Cod sursa(job #555706)

Utilizator bog29Antohi Bogdan bog29 Data 15 martie 2011 18:23:04
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#define dmax 500004
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");

long long n, x[dmax], k[dmax], pi[dmax];

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


int main()
{	
	int i,r;
	
	in>>n;
	for(i=1;i<=n;i++)
		in>>x[i];
	in.close();
	
	for(i=1 ;i<n ; i++)
		k[i] = x[i+1] - x[i];
	
	prefix();
	
	r = n-1 - pi[n-1];
	
	out<<r<<'\n';
	
	for(i=1; i<=r; i++)
		out<<k[i]<<'\n';
	
	out.close();
	return 0;
}