UVA 104 : Arbitrage

arbitrage

#include <iostream>
#include <stack>
 
using namespace std;
 
static const int MAX_SIZE = 20;
 
struct Cell {
    double profit; // the best profit so far
    int	action; // index to the currency that yields the current profit
} Profits[MAX_SIZE][MAX_SIZE][MAX_SIZE];
 
int main() {
    int n; // dimension
    bool bHasMadeProfit;
 
    while ( cin >> n ) {
        bHasMadeProfit = false;
 
        // clear the table
        for ( int i=0; i<n; i++ ) {
            for ( int j=0; j<n; j++ ) {
                for ( int k=0; k<n; k++ ) {
                    Profits[i][j][k].profit = 0.0;
                    Profits[i][j][k].action = -1;
                }
            }
        }
 
        // init table
        for ( int r=0; r<n; r++ ) {
            for ( int c=0; c<n; c++ ) {
                if ( c != r) {
                    cin >> Profits[0][r]1.profit = 1.0;
                }
            }
        }
 
                for ( int trial = 1; trial < n; trial++ ) {
            for ( int r=0; r<n; r++ ) {
                for ( int c=0; c<n; c++ ) {
                    // find the max profit from currency r to currency c
                    for ( int k=0; k<n; k++ ) {
                        double val = Profits[trial-1][r][k].profit * Profits[0][k]1.profit < val) {
                            Profits[trial][r]1.action = k;
                        }
                    }
                }
 
                                if ( Profits[trial][r][r].profit > 1.01 ) {
                    bHasMadeProfit = true;
 
                    // backtracking
                    stack<int> outsequence;
                    outsequence.push(r); // add another action
 
                    int prevAction = Profits[trial][r][r].action;
                    for ( int step = trial-1; step>=0; step-- ) {
                        outsequence.push(prevAction);
                        prevAction = Profits[step][r][prevAction].action;
                    }
 
                    //print the first action ( choosing currency r )
                    cout << r + 1;
 
                    while ( ! outsequence.empty() ) {
                        cout << " " << outsequence.top() + 1;
                        outsequence.pop();
                    }
 
                    cout << endl;
                    break;
                } // end of c-loop
                        } // end of r-loop
            if ( bHasMadeProfit ) {
                break;
            }
 
        } // end trial for-loop
 
        if ( ! bHasMadeProfit ) {
            cout << "no arbitrage sequence exists" << endl;
        }
    } // end while
 
    return 0;
}