Cod sursa(job #613923)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 5 octombrie 2011 09:00:32
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>

const long long N = 500005;

int n, pi[N];

long long a[N], v[N];

void read() {
	scanf("%d", &n);
	
	for (int i = 0; i < n; ++i)
		scanf("%lld", &v[i]);
}

void init() {
	for (int i = 1; i < n; ++i)
		a[i] = v[i] - v[i - 1];
}

void prefix() {
	pi[1] = 0;
	
	int lp = 0;
	
	for (int i = 2; i < n; ++i) {
		while (lp && a[lp + 1] != a[i])
			lp = pi[lp];
		
		if (a[lp + 1] == a[i])
			++lp;
		
		pi[i] = lp;
	}
}

int main() {
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	
	read();
	
	init();
	
	prefix();

	printf("%d\n", n - 1 - pi[n - 1]);
	
	for (int i = 1; i <= n - 1 - pi[n - 1]; ++i)
		printf("%d\n", a[i]);
	
	return 0;
}