Submission

Score: 100

User: Gump2011

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-08 17:24:06

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<double>> c(n+1, vector<double>(n+1));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> c[i][j];
        }
    }

    vector<vector<vector<double>>> dp(n+1,
        vector<vector<double>>(n+1, vector<double>(n+1,0)));

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[1][i][j] = c[i][j];

    for(int l=1;l<=n;l++){
        for(int i=1;i<=n;i++){
            if(dp[l][i][i] > 1.01){
                cout << i << " " << l << "\n";
                return 0;
            }
        }

        if(l==n) break;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    dp[l+1][i][j] = max(dp[l+1][i][j],
                                        dp[l][i][k]*c[k][j]);
                }
            }
        }
    }

    cout << -1 << "\n";
}