Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 21:13:31

#include<iostream>
#include<vector>
#include<queue>
#include<iomanip>

using namespace std;
vector<vector<float>> convertion_rate;
int c;

int min_length = 1e9;
vector<int> path;

void recursive(int currency, float worth, vector<int> history) {
	if (history.size() > c) return;
	if (worth >= 1.01 && min_length > history.size() && currency == 0) {


		min_length = history.size();
		path = history;
		return;
	};

	for (int i = 0; i < c; i++) {
		vector<int> newHistory = history;
		newHistory.push_back(i);
		
		recursive(i, worth * convertion_rate[currency][i], newHistory);	
	}
}

int main() {
	cin >> c;
	convertion_rate.resize(c, vector<float>(c));

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

	recursive(0, 1.00, {0});
	if (!path.size()) {
		cout << -1;
		return 0;
	}

	for (int i = 0; i < path.size() - 1; i++) {
		cout << path[i] + 1 << " ";
	}

	return 0;
}