Cod sursa(job #18550)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 18 februarie 2007 12:36:35
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.74 kb
#include<stdio.h>

#define NMAX 500100

void read();
void prefix();

long long V[NMAX];
long long pi[NMAX];
int N;

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

     read();
	return 0;
}

void read()
{
	int i, min;
     long long a, b;
     
	scanf("%d", &N);

     scanf("%lld", &a);
     for(i = 1; i < N; i++)
     {
     scanf("%lld", &b);
     V[i] = b - a;
     a = b;
     }
     prefix();
	min = N - 1 - pi[N - 1];
     printf("%d\n", min);
     for(i = 1; i <= min; i++)
     printf("%lld\n", V[i]);
}

void prefix()
{
	int i, k = 0;

	pi[1] = 0;
     for(i = 2; i < N; i++)
     {
     	while(V[i] != V[k + 1] && k > 0)
          k = pi[k];
          if(V[i] == V[k + 1]) k++;
          pi[i] = k;
     }
}