2013年8月18日

UVa 104 - Arbitrage

#include <cstdio>
#include <cstring>

double max(double a, double b) {
  return a > b ? a : b;
}

int mid[20][20][20];

void showPath(int a, int b, int s) {
  if (mid[a][b][s] == -1) {
    printf("%d %d", a + 1, b + 1);
    return;
  }
  showPath(a, mid[a][b][s], s - 1);
  printf(" %d", b + 1);
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    memset(mid, -1, sizeof(mid));
    double change[20][20][20] = {};
    for (int a = 0; a < n; a++) {
      for (int b = 0; b < n; b++) {
        if (a == b) {
          change[a][b][1] = 1.0;
        } else {
          scanf("%lf", &change[a][b][1]);
        }
      }
    }
    bool find = false;
    for (int s = 2; s <= n && !find; s++) {
      for (int k = 0; k < n; k++) {
        for (int a = 0; a < n; a++) {
          for (int b = 0; b < n; b++) {
            if (change[a][k][s - 1] * change[k][b][1] > change[a][b][s]) {
              change[a][b][s] = change[a][k][s - 1] * change[k][b][1];
              mid[a][b][s] = k;
            }
          }
        }
      }
      for (int a = 0; a < n && !find; a++) {
        if (change[a][a][s] >= 1.01) {
          showPath(a, a, s);
          puts("");
          find = true;
        }
      }
    }
    if (!find) {
      puts("no arbitrage sequence exists");
    }
  }
  return 0;
}

沒有留言:

張貼留言