Cod sursa(job #18220)

Utilizator MariusMarius Stroe Marius Data 18 februarie 2007 10:49:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.89 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;
	}
	P[N + 1] = P[N] + 1;
	for (i = N; P[i] > 0; -- i)
		if (((i - P[i]) % P[i] == 0) && (P[i + 1] == P[i] + 1))
			return (i - P[i]);
	return 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;
}