Cod sursa(job #18439)

Utilizator mockeBarca Cristian Mihai mocke Data 18 februarie 2007 12:12:35
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.67 kb
#include <stdio.h>
#define NMAX 500012

long long A[NMAX], S[NMAX];
int Pi[NMAX];
int N, i, j, k, per;

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

     scanf("%d", &N);

     for (i = 0; i < N; i++) scanf("%lld", &A[i]);

     for (i = 1; i < N; i++) S[i] = A[i] - A[i-1];

     k = 0;
     Pi[1] = 0;

     for (i = 2; i < N; i++)
     {
          while (k > 0 && S[k+1] != S[i]) k = Pi[k];

          if (S[k+1] == S[i]) k++;

          Pi[i] = k;
     }

     per = N - 1 - Pi[N - 1];

     printf("%d\n", per);

     for (i = 1; i <= per; i++) printf("%lld\n", S[i]);

     return 0;
}