Submission

Score: 100

User: C12

Problemset: forex

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-07 00:33:50

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    double cost[31][31] = {0};

    int out[31];

    cin >> n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin >> cost[i][j];
        }
        out[i] = INT_MAX;
    }

    for(int i = 0;i < n;i++){
        int b = 1;
        int c = 0;
        
        double prev[31];
        for(int j = 0;j < n;j++){
            prev[j] = 0;
        }
        prev[i] = 1;

        while(b){
            b = 0;
            c++;
            double cur[31];
            for(int i = 0;i < n;i++){
                cur[i] = prev[i];
            }

            for(int j = 0;j < n;j++){
                for(int k = 0;k < n;k++){
                    if(prev[j] * cost[j][k] > cur[k]){
                        cur[k] = prev[j] * cost[j][k];
                        b = 1;
                    }
                }
            }

            if(cur[i] >= 1.01){
                out[i] = c;
                break;
            }

            for(int i = 0;i < n;i++){
                prev[i] = cur[i];
            }
        }    
    }
    int idx = 0;
    int mx = out[0];
    for(int i = 1;i < n;i++){
        if(out[i] < mx){
            mx = out[i];
            idx = i;
        }
    }

    if(mx == INT_MAX){
        cout << -1;
    }
    else{
        cout << (idx+1) << ' ' << mx;
    }
    return 0;
}