Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

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

#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];

    vector<vector<double>> dp(n, vector<double>(n+1, 0.0));
    vector<vector<int>> pre(n, vector<int>(n+1, -1));

    dp[0][0] = 1.0;

    int steps = -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 (val > 1.01 && steps == -1) {
                        steps = k;
                        endCurrency = v;
                    }
                }
            }
        }
        if (steps != -1) break;
    }

    if (steps == -1) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> path(steps+1);
    int cur = endCurrency;
    for (int k = steps; k >= 1; k--) {
        path[k] = cur + 1;
        cur = pre[cur][k];
    }
    path[0] = 1;

    for (int i = 0; i <= steps; i++) {
        cout << path[i];
        if (i < steps) cout << " ";
    }
    cout << endl;
}