Submission

Score: 100

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 22:12:54

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

    int bestStart = -1;
    int bestSteps = n + 1;

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

        int stepsFound = -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++) {
                    dp[v][k] = max(dp[v][k], dp[u][k-1] * rate[u][v]);
                }
            }

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

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

    if (bestStart == -1) {
        cout << -1 << endl;
    } else {
        cout << bestStart + 1 << " " << bestSteps << endl;
    }

    return 0;
}