#include <cstdio>
#include <cmath>
#include <cstring>

void read_ts(const char* filename, int &len, int* &ts) {
  FILE* f = fopen(filename, "r");
  fscanf(f, "%d", &len);
  ts = new int[len];
  for (int i = 0; i < len; ++i) {
    fscanf(f, "%d", &(ts[i]));
  } 
  fclose(f);
}

double compute_distance(int lena, int* tsa, int lenb, int* tsb) {
  double* f1 = new double[lenb];
  double* f2 = new double[lenb];
  f1[0] = fabs(tsa[0] - tsb[0]);
  for (int j = 1; j < lenb; ++j) {
    f1[j] = f1[j-1] + fabs(tsa[0]-tsb[j]);
  }
  for (int i = 1; i < lena; ++i) {
    f2[0] = f1[0] + fabs(tsa[i]-tsb[0]); 
    for (int j = 1; j < lenb; ++j) {
      f2[j] = f1[j-1];
      if (f1[j] < f2[j]) {
        f2[j] = f1[j];
      }
      if (f2[j-1] < f2[j]) {
        f2[j] = f2[j-1];
      }
      f2[j] += fabs(tsa[i]-tsb[j]);
    }
    double* tmp = f1;
    f1 = f2;
    f2 = tmp;
  }
  double ans = f1[lenb - 1];
  delete [] f1;
  delete [] f2;
  return ans;
}

int main(int narg, char* args[]) {
  char fn[100];
  double minv = 1e30;
  int di, dj;
  for (int i = 1; i <= 10; ++i) { 
    int lena;
    int* tsa;
    sprintf(fn, "./Data/%04d.dat", i);
    read_ts(fn, lena, tsa);
    for (int j = i+1; j <= 10; ++j) {
      int lenb;
      int* tsb;
      sprintf(fn, "./Data/%04d.dat", j);
      read_ts(fn, lenb, tsb);
      double dis =  compute_distance(lena, tsa, lenb, tsb);
      if (dis < minv) {
        minv = dis;
        di = i;
        dj = j;
      } else if (dis == minv) {
        printf("same!\n");
      }
      printf("Ans[%d,%d] = %lf\n", i, j, dis);
      delete [] tsb;
    }
    delete [] tsa;
  }
  printf("%04d.dat %04d.dat %lf\n", di, dj, minv);
  return 0;
}