Cod sursa(job #2014791)

Utilizator mihai.alphamihai craciun mihai.alpha Data 24 august 2017 14:06:30
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>

#define MAXN 500000

FILE *fin, *fout;

int N;
int x[MAXN + 1];
int dif[MAXN + 1];
int pi[MAXN + 1];

int main() {
	fin = fopen("reguli.in", "r");
	fout = fopen("reguli.out", "w");
	fscanf(fin, "%d", &N);
	for (int i = 1; i <= N; i++)
		fscanf(fin, "%d", &x[i]), dif[i - 1] = x[i] - x[i - 1];
	int k = 0, M = N - 1;
	pi[1] = 0;
	for (int i = 2; i <= M; i++) {
		while (k > 0 && dif[k + 1] != dif[i])
			k = pi[k];
		if (dif[k + 1] == dif[i])
			k++;
		pi[i] = k;
	}
	int l = M - pi[M];
	fprintf(fout, "%d\n", l);
	for (int i = 1; i <= l; i++)
		fprintf(fout, "%d\n", dif[i]);
	fclose(fin);
	fclose(fout);
	return 0;
}