Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 21:52:25

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

int main() {
    int n;
    cin >> n;

    vector<vector<double>> rate(n, vector<double>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> rate[i][j]; // get input

    int bestStart = -1;
    int bestSteps = n + 1;
    vector<int> bestPath;

    for (int start = 0; start < n; start++) {
        vector<vector<double>> dp(n, vector<double>(n+1, 0.0));
        vector<vector<int>> pre(n, vector<int>(n+1, -1));
        dp[start][0] = 1.0;

        int stepsFound = -1;
        int endCurrency = -1;

        for (int k = 1; k <= n; k++) {
            for (int u = 0; u < n; u++) {
                if (dp[u][k-1] == 0) continue;
                for (int v = 0; v < n; v++) {
                    double val = dp[u][k-1] * rate[u][v];
                    if (val > dp[v][k]) {
                        dp[v][k] = val;
                        pre[v][k] = u;
                    }
                }
            }

            if (dp[start][k] > 1.01) {
                stepsFound = k;
                endCurrency = start;
                break;
            }
        }

        if (stepsFound != -1 && stepsFound < bestSteps) {
            bestSteps = stepsFound;
            bestStart = start;

            vector<int> path(stepsFound+1);
            int cur = endCurrency;
            for (int k = stepsFound; k >= 1; k--) {
                path[k] = cur + 1; // convert to base 1
                cur = pre[cur][k];
            }
            path[0] = start + 1;
            bestPath = path;
        }
    }

    if (bestStart == -1) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < bestSteps; i++) {
            cout << bestPath[i];
            if (i < bestSteps) cout << " ";
        }
        cout << endl;
    }

    return 0;
}