Cod sursa(job #1479591)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 31 august 2015 17:28:49
Problema Reguli Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <stdio.h>
#define MAX 500005

int n, m, x[MAX], i, p[MAX];

void prefix();

int main(){
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	scanf("%d%d", &n, &x[0]);
	for(i = 1; i < n; i++)
		scanf("%d", &x[i]);
	for(i = n - 1; i > 0; i--)
		x[i] -= x[i - 1];
	prefix();
	m = --n;
	while(p[m] == p[m - 1] + 1)
		m--;
	m = 2 * m <= n ? m : n;
	printf("%d\n", m);
	for(i = 1; i <= m; i++)
		printf("%d\n", x[i]);
	return 0;
}

void prefix(){
	int i, k = 0;
	for(i = 2; i < n; i++){
		while(k > 0 && x[k + 1] != x[i])
			k = p[k];
		if(x[k + 1] == x[i])
			k++;
		p[i] = k;
	}
}