Cod sursa(job #1428104)

Utilizator hrazvanHarsan Razvan hrazvan Data 3 mai 2015 18:15:53
Problema Reguli Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#define MAXN 500000
int v[MAXN], phi[MAXN];

int main(){
  FILE *in = fopen("reguli.in", "r");
  int n, i, last, x, k = -1;
  fscanf(in, "%d%d", &n, &last);
  phi[0] = -1;
  for(i = 1; i < n; i++){
    fscanf(in, "%d", &x);
    v[i - 1] = x - last;
    if(i != 1){
      while(k != -1 && v[i - 1] != v[k + 1])
        k = phi[k];
      if(v[i - 1] == v[k + 1])
        k++;
      phi[i - 1] = k;
    }
    last = x;
  }
  fclose(in);
  int rez = -1, j;
  char g = 0;
  i = n - 2;
  while(i >= 0 && rez == -1 && 2 * (phi[i] + 1) < i)
    i--;
  if(i >= 0){
    rez = n - 1 - (phi[i] + 1);
    j = 0;
    for(i++; i < n - 1; i++){
      if(v[i] != v[j])
        g = 1;
    }
    if(g)
      rez = n - 1;
  }
  else
    rez = n - 1;
  FILE *out = fopen("reguli.out", "w");
  fprintf(out, "%d\n", rez);
  for(i = 0; i < rez; i++)
    fprintf(out, "%d\n", v[i]);
  fclose(out);
  return 0;
}