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;
}