Cod sursa(job #1227274)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 9 septembrie 2014 19:57:07
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>
#define DIM 500005

using namespace std;

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

int n;

int A[DIM], Pi[DIM];

int main() {
	f >> n;
	for (int i = 1; i <= n; ++i)
		f >> A[i];
	for (int i = 1; i <= n; ++i)
		A[i] = A[i + 1] - A[i];
	--n;
	for (int i = 2; i <= n; ++i) {
		int q = Pi[i-1];
		while (q && A[i] != A[q + 1])
			q = Pi[q];
		if (A[i] == A[q + 1])
			++q;
		Pi[i] = q;
	}
	n -= Pi[n];
	g << n << "\n";
	for (int i = 1; i <= n; ++i)
		g << A[i] << "\n";
	return 0;
}