Cod sursa(job #791975)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 25 septembrie 2012 22:44:46
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#define NMAx 500100
using namespace std;

long long V[NMAx];
int N,Sol,Fail[NMAx];

void Afis() {
	
	ofstream out("reguli.out");
	out<<Sol<<'\n';
	
	for(int i=1;i<=Sol;i++)
		out<<V[i]<<'\n';
	
	out.close();
	
}
void Solve() {
	
	int i,e;
	
	Fail[1]=0;
	for(i=2,e=0;i<N;i++) {
		
		while(e && V[e+1]!=V[i])
			e=Fail[e];
		
		if(V[e+1]==V[i])
			e++;
		
		Fail[i]=e;
		}
	
	for(--i;!Sol;i--)
		if(Fail[i] && i%(i-Fail[i])==0)
			Sol=i-Fail[i];
	
}
void Citire() {

	ifstream in("reguli.in");
	in>>N>>V[1];
	
	for(int i=2;i<=N;i++) {
		in>>V[i];
		V[i-1]=V[i]-V[i-1];
		}
	
	in.close();

}
int main() {
	
	Citire();
	Solve();
	Afis();
	
	return 0;
	
}