Cod sursa(job #1991454)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 16 iunie 2017 20:33:05
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>

typedef long long i64;
const int MAXN = 5e5;

i64 x[MAXN];
int pi[MAXN];

int main() {
  int n, k;
  i64 curr, ant;
  FILE *f = fopen("reguli.in", "r");
  fscanf(f, "%d%lld", &n, &curr);
  --n;
  for (int i = 1; i <= n; ++i) {
    ant = curr;
    fscanf(f, "%lld", &curr);
    x[i] = curr - ant;
  }
  fclose(f);
  k = 0;
  for (int q = 2; q <= n; ++q) {
    while ((k > 0) && (x[q] != x[k + 1])) {
      k = pi[k];  
    }             
    if (x[q] == x[k + 1]) {
      ++k;
    }
    pi[q] = k;
  }
  n -= pi[n];
  f = fopen("reguli.out", "w");
  fprintf(f, "%d\n", n);
  for (int i = 1; i <= n; ++i) {
    fprintf(f, "%lld\n", x[i]); 
  }
  fclose(f);
  return 0;
}