Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 21:07:36

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

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

int min_length = 999;
vector<int> path;

void recursive(int currency, float worth, int length, vector<int> history) {
	if (length > c) return;
	if (worth >= 1.01 && min_length > length && currency == 0) {
		min_length = length;
		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], length + 1, 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(1, 1.00, 0, {1});
	if (path.size() == 1) {
		cout << -1;
		return 0;
	}

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

	return 0;
}