Cod sursa(job #18236)

Utilizator MariusMarius Stroe Marius Data 18 februarie 2007 10:56:07
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.77 kb
#include <cstdio>
using namespace std;

const char iname[] = "reguli.in";
const char oname[] = "reguli.out";

typedef long long i64;

#define MAX_N 500007

int N;

i64 A[MAX_N];

int P[MAX_N];


int solve(void)
{
	int i;
	int k;
	P[1] = 0;
	k = 0;
	for (i = 2; i <= N; ++ i) {
		while (k > 0 && A[k + 1] != A[i])
			k = P[k];
		if (A[k + 1] == A[i])
			k ++;
		P[i] = k;
	}
	return N - P[N];
}

int main(void)
{
	freopen(iname, "r", stdin);
	int i;
	i64 lo;
	i64 hi;
	for (scanf("%d\n", & N), i = 0; i < N; ++ i) {
		scanf("%lld\n", & hi);
		if (i > 0)
			A[i] = hi - lo;
		lo = hi;
	}
	N -= 1;
	int ret = solve();
	freopen(oname, "w", stdout);
	printf("%d\n", ret);
	for (i = 1; i <= ret; ++ i)
		printf("%lld\n", A[i]);
	return 0;
}