Cod sursa(job #1135561)

Utilizator harababurelPuscas Sergiu harababurel Data 8 martie 2014 00:01:16
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 500005
using namespace std;

int n, x[nmax], pi[nmax];
vector <int> v;

void buildPi() {
	pi[0] = pi[1] = 0;
	for(int i=2; i<v.size(); i++) {
		int j = pi[i-1];

		while(1) {
			if(v[i] == v[j]) { pi[i] = j+1; break; }
			if(j == 0) { pi[i] = 0; break; }
			j = pi[j];
		}
	}
}

int main() {
	ifstream f("reguli.in");
	ofstream g("reguli.out");

	f>>n;
	for(int i=0; i<n; i++) f>>x[i];
	for(int i=1; i<n; i++) v.push_back(x[i]-x[i-1]);

	buildPi();

	int pos = v.size() - 1;
	while(pos > 0 && pi[pos] == pi[pos-1] + 1 && pi[pos]>1) pos--;

	g<<pos<<"\n";
	for(int i=0; i<pos; i++) g<<v[i]<<"\n"; 

	//for(int i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<"\n";
	//for(int i=0; i<v.size(); i++) cout<<pi[i]<<" "; cout<<"\n";

	return 0;
}