Submission

Score: 100

User: C12

Problemset: forex

Language: cpp

Time: 0.003 second

Submitted On: 2025-12-31 23:20:54

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

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;

float change[32][32];
float mx[32][32];

void solve(){
    int n;

    cin >> n;

    queue<pair<int,pair<int,float>>>q;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin >> change[i][j];
            if(i == j && change[i][j] >= 1.01){
                cout << (i + 1) << ' ' << 1;
                return;
            }
            // cout << change[i][j] << '\n';
        }
        mx[i][i] = 1.00;
        q.push(mp(i,mp(i,1.00)));
    }

    int size,cnt,ori,num;
    float cur,icur;

    cnt = 0;

    while(1){
        cnt++;
        size = q.size();
        while(size-- && !q.empty()){
            ori = q.front().f;
            num = q.front().s.f;
            cur = q.front().s.s;
            // cout << ori << ' ' << num << ' ' << cur << '\n';
            q.pop();
            for(int i = 0;i < n;i++){
                icur = cur * change[num][i];
                if(icur <= mx[ori][i]){
                    continue;
                }
                if(icur * change[i][ori] >= 1.01){
                    cout << (ori + 1) << ' ' << (cnt + 1);
                    return; 
                }
                mx[ori][i] = icur;
                q.push(mp(ori,mp(i,icur)));
            }
        }
        if(q.empty()){
            cout << -1;
            return;
        }
        // cout << '\n';
    }

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

    ll q;
 
    // cin >> q;

    // while(q--)
        solve(); 

    return 0;
}