Cod sursa(job #1479596)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 31 august 2015 17:43:14
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <fstream>
#define MAX 500005
using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n, x[MAX], i, p[MAX];

void prefix();

int main(){
	fin >> n;
	n--;
	for(i = 0; i <= n; i++)
		fin >> x[i];
	for(i = n; i > 0; i--)
		x[i] -= x[i - 1];
	prefix();
	fout << n - p[n] << "\n";
	for(i = 1; i <= n - p[n]; i++)
		fout << x[i] << "\n";
	return 0;
}

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