Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 21:38:24

#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 (dp[0][k] > 1.01) {
            steps = k;
            endCurrency = 0;
            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; // what the fuck
    return 0;
}