Cod sursa(job #23289)

Utilizator MariusMarius Stroe Marius Data 28 februarie 2007 16:22:13
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
using namespace std;

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

#define MAX_N 500000

typedef long long i64;

i64 A[MAX_N];

int P[MAX_N];


int main(void)
{
	freopen(iname, "r", stdin);
	int n;
	int i;
	i64 lo, hi;
	scanf("%d", & n);
	scanf("%lld", & lo);
	for (i = 1; i < n; ++ i)
		scanf("%lld", & hi), A[i] = hi - lo, lo = hi;
	int k;
	P[1] = 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;
	}
	freopen(oname, "w", stdout);
	int res = n - 1 - P[n - 1];
	printf("%d\n", res);
	for (i = 1; i <= res; ++ i)
		printf("%lld\n", A[i]);
	return 0;
}