Cod sursa(job #1108486)

Utilizator danny794Dan Danaila danny794 Data 15 februarie 2014 19:12:39
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>

typedef long long ll;
const int NMAX = 500005;

using namespace std;

int N, last;
ll array[NMAX];
int pi[NMAX];

void read() {
  freopen("reguli.in", "r", stdin);
  freopen("reguli.out", "w", stdout);
  scanf("%d", &N);
  ll x, y;
  scanf("%lld", &x);
  for(int i = 1; i < N; i++) {
    scanf("%lld", &y);
    array[i] = y - x;
    x = y;
  }
}

void computePi() {
  for(int i = 2; i < N; i++) {
    pi[i] = pi[i - 1];
    while( pi[i] != 0 && array[i] != array[pi[i] + 1] )
      pi[i] = pi[pi[i]];
    if (array[i] == array[pi[i] + 1])
      pi[i]++;
    if(pi[i] == 1)
      last = i;
  }

}

int main() {
  read();
  computePi();
  printf("%i\n", last - 1);
  for(int i = 1; i < last; i++)
    printf("%lld\n", array[i]);
  return 0;
}