Submission

Score: 0

User: krittaphot

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-07 14:22:19

#include <bits/stdc++.h>

using namespace std;
int n;
double memo[31][31];
int solve(int start,int now,int cnt,double mutiply,vector<vector<double>>& currency,vector<int>& use){
    if(start == now && mutiply >= 1.01){
        return cnt;
    }
    if(memo[now][cnt] >= mutiply) return INT_MAX;
    memo[now][cnt] = mutiply;
    int ans = INT_MAX;
    for(int i = 1; i <= n; i++){
        if(i == now) continue;
        if(use[i] && i != start) continue;
        use[i] = 1;
        ans = min(ans,solve(start,i,cnt+1,mutiply*currency[now][i],currency,use));
        use[i] = 0;
    }
    return ans;
}
int main()
{
    cin >> n;
    vector<vector<double>> currency(n+1, vector<double>(n+1));
    vector<int> use(n+1,false);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> currency[i][j];
        }
    }
    int ans = INT_MAX;
    int start = 0;
    for(int i = 1; i <= n; i++){
        use[i] = 1;
        int res = solve(i,i,0,1.0,currency,use);
        if(res < ans){
            ans = res;
            start = i;
        }
        use[i] = 0;
    }
    if(ans == INT_MAX){
        cout << "-1" << endl;
    } else {
        cout << start << " " << ans << endl;
    }
}