Submission

Score: 0

User: qweqwe

Problemset: forex

Language: cpp

Time: 1.094 second

Submitted On: 2025-10-22 17:22:01

#include <bits/stdc++.h>
#define speed cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define db long double
using namespace std;

vector<vector<db>> moner(31,vector<db>(31));

int main(){
	speed;
	int n;cin >> n;
	const int pow=1<<n;
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			cin >> moner[i][j];
		}
	}int mn=n;
	vector<int> sortt;
	for (int i=1;i<pow;i++){
		db mx=0;int st=-1;
		bitset<31> bitn(i); // 1<=n<=30
		if (bitn.count()>mn) continue;
		vector<int> idx;
		//cout << mn << "\n";
		for (int j=0;j<n;j++){
			if (bitn[j]==1){
				//cout << j << "\n";
				if (st==-1) st=j;
				idx.push_back(j);
			}
		}sort(idx.begin(),idx.end());
		int size=idx.size();
		do{
			if (mx>(db)1.01) break;
			db sum=1;
			for (int j=0;j<size-1;j++){
				sum*=moner[idx[j]][idx[j+1]];
			}sum*=moner[idx[size-1]][idx[0]];
			mx=max(mx,sum);
		}while (next_permutation(idx.begin(),idx.end()));
		//cout << mx << "\n";
		if (mx>(db)1.01 && size<=mn){
			if (size<mn){
				mn=size;
				sortt.clear();
			}
			sortt.push_back(st);
		}
		/*
		for (int j=0;j<n;j++){
			cout << bitn[j] << " "; // 1,2^1,2^2 etc.
		}cout << "\n";
		*/
	}sort(sortt.begin(),sortt.end());
	if (sortt.empty()) cout << -1;
	else cout << sortt[0]+1 << " " << mn;
	return 0;
}
/*
3
1.00 1.20 0.89
0.88 1.00 5.10
1.10 0.15 1.00
1 2
1 -> 2

2
1.00 2.00
0.45 1.00
-1

5
1.00 0.90 0.98 0.70 0.67
0.90 1.00 0.80 0.99 0.45
0.98 1.03 1.00 0.98 0.97
0.70 0.98 1.00 1.00 0.20
0.67 0.45 0.97 0.20 1.00
2 3
2 -> 4 -> 3

10
1.00 0.90 0.98 0.70 0.67 1.00 0.90 0.98 0.70 0.67
0.90 1.00 0.80 0.99 0.45 0.90 1.00 0.80 0.99 0.45
0.98 1.03 1.00 0.98 0.97 0.98 1.03 1.00 0.98 0.97
0.70 0.98 1.00 1.00 0.20 0.70 0.98 1.00 1.00 0.20
0.67 0.45 0.97 0.20 1.00 0.67 0.45 0.97 0.20 1.00
1.00 0.90 0.98 0.70 0.67 1.00 0.90 0.98 0.70 0.67
0.90 1.00 0.80 0.99 0.45 0.90 1.00 0.80 0.99 0.45
0.98 1.03 1.00 0.98 0.97 0.90 1.00 0.80 0.99 0.45
0.70 0.98 1.00 1.00 0.20 0.90 1.00 0.80 0.99 0.45
0.67 0.45 0.97 0.20 1.00 0.90 1.00 0.80 0.99 0.45
*/