104 - Arbitrage

Background

The use of computers in the finance industry has been marked with controversy lately as programmed trading -- designed to take advantage of extremely small fluctuations in prices -- has been outlawed at many Wall Street firms. The ethics of computer programming is a fledgling field with many thorny issues.

The Problem

Arbitrage is the trading of one currency for another with the hopes of taking advantage of small differences in conversion rates among several currencies in order to achieve a profit. For example, if $1.00 in U.S. currency buys 0.7 British pounds currency, £1 in British currency buys 9.5 French francs, and 1 French franc buys 0.16 in U.S. dollars, then an arbitrage trader can start with $1.00 and earn dollars thus earning a profit of 6.4 percent.
You will write a program that determines whether a sequence of currency exchanges can yield a profit as described above.
To result in successful arbitrage, a sequence of exchanges must begin and end with the same currency, but any starting currency may be considered.

The Input

The input file consists of one or more conversion tables. You must solve the arbitrage problem for each of the tables in the input file.
Each table is preceded by an integer n on a line by itself giving the dimensions of the table. The maximum dimension is 20; the minimum dimension is 2.
The table then follows in row major order but with the diagonal elements of the table missing (these are assumed to have value 1.0). Thus the first row of the table represents the conversion rates between country 1 and n-1 other countries, i.e., the amount of currency of country i (  ) that can be purchased with one unit of the currency of country 1.
Thus each table consists of n+1 lines in the input file: 1 line containing n and n lines representing the conversion table.

The Output

For each table in the input file you must determine whether a sequence of exchanges exists that results in a profit of more than 1 percent (0.01). If a sequence exists you must print the sequence of exchanges that results in a profit. If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.

Because the IRS (United States Internal Revenue Service) notices lengthy transaction sequences, all profiting sequences must consist of n or fewer transactions where n is the dimension of the table giving conversion rates. The sequence 1 2 1 represents two conversions.
If a profiting sequence exists you must print the sequence of exchanges that results in a profit. The sequence is printed as a sequence of integers with the integer i representing the  line of the conversion table (country i). The first integer in the sequence is the country from which the profiting sequence starts. This integer also ends the sequence.
If no profiting sequence of n or fewer transactions exists, then the line

no arbitrage sequence exists

should be printed.

Sample Input

3
1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

Sample Output

1 2 1
1 2 4 1
no arbitrage sequence exists

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40

---

問題敘述

此問題首先會輸入國家的數量，並且輸入每個國家和每個國家的匯率兌換表(同個國家的兌換匯率不會輸入，因為一定是1)，要您求出可以經由最少的兌換次數來達到獲利超過1%的兌換方式(可以在任何國家的幣紙上獲利)，若有兩種以上最少兌換次數可以獲利超過1%，隨便印出一種兌換方法即可，若找不到兌換方法，則印出"no arbitrage sequence exists"。

解題思路

此題使用Dynamic programming來解，首先求出各個國家只兌換1次可以得到的最佳解(也就是初始的匯率兌換表)，再利用只兌換1次的最佳解求出只兌換2次的最佳解，接著再利用只兌換2次的最佳解求出只兌換3次的最佳解...依此類推，一直求到有國家自己兌換自己可以超過1.01就表示找到解了，若一直求到n次兌換都找不到解，表示此解找不到。

c++ 程式碼

#include <iostream>
#include <vector>
using namespace std;

void findPath(vector< vector< vector<int> > >& path, int startCountry, int endCountry, int step) {
    if (path[step][startCountry][endCountry] != -1) {
        findPath(path, startCountry, path[step][startCountry][endCountry], step - 1);
        cout << " " << path[step][startCountry][endCountry] + 1;
    }
}

int main() {
    int countryNum;

    while (cin >> countryNum) {
         vector< vector< vector<double> > > bestRateEachStep(countryNum, vector< vector<double> >(countryNum,
                      vector<double>(countryNum, 0)));
         vector< vector< vector<int> > > path(countryNum, vector< vector<int> >(countryNum,
                      vector<int>(countryNum, -1)));
         int startCountry = -1;
         int lastStep = -1;

        for (int i=0; i<countryNum; i++) {
            for (int j=0; j<countryNum; j++) {
                if (i == j)
                    bestRateEachStep[0][i][j] = 1;
                else
                    cin >> bestRateEachStep[0][i][j];
            }
        }
        for (int step=1; step<countryNum; step++) {
            for (int k=0; k<countryNum; k++) {
                for (int i=0; i<countryNum; i++) {
                    for (int j=0; j<countryNum; j++) {
                        if (bestRateEachStep[step - 1][i][k] * bestRateEachStep[0][k][j] > bestRateEachStep[step][i][j]) {
                            bestRateEachStep[step][i][j] = bestRateEachStep[step - 1][i][k] * bestRateEachStep[0][k][j];
                            path[step][i][j] = k;
                        }
                    }
                }
            }
            for (int i=0; i<countryNum; i++) {
                if (bestRateEachStep[step][i][i] > 1.01) {
                    startCountry = i;
                    lastStep = step;
                    break;
                }
            }
            if (startCountry != -1)
                break;
        }
        if (startCountry == -1)
            cout << "no arbitrage sequence exists\n";
        else {
            cout << startCountry + 1;
            findPath(path, startCountry, startCountry, lastStep);
            cout << " " << startCountry + 1 << endl;
        }
    }

    return 0;
}