Submission

Score: 0

User: goine

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-10 21:16:16

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

vector<vector<float>> conversion_rate;
int c;

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

void recursive(int currency, double worth, vector<int> history) {
    // Stop if path is too long
    if (history.size() > c + 1) return;

    // Check if arbitrage cycle found
    if (currency == 0 && history.size() > 1 && worth > 1.01 - 1e-9) {
        if (history.size() < min_length) {
            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 * conversion_rate[currency][i], newHistory);
    }
}

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

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

    recursive(0, 1.0, {0});

    if (path.empty()) {
        cout << -1 << endl;
        return 0;
    }

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

    return 0;
}