#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>

std::vector<double> gearbox_values = { -1, 1, 6.0 / 5, 3.0 / 2, 9.0 / 5, 2.0, 5.0 / 2, 3.0, 5.0 / 6, 2.0 / 3, 5.0 / 9, 1.0 / 2, 2.0 / 5, 1.0 / 3 };
std::vector<std::string> gearbox_strings = { "1:-1", "1:1", "6:5", "3:2", "9:5", "2:1", "5:2", "3:1", "5:6", "2:3", "5:9", "1:2", "2:5", "1:3" };

size_t myPow(size_t x, size_t p)
{
    if (p == 0) return 1;
    if (p == 1) return x;

    size_t tmp = myPow(x, p / 2);
    if (p % 2 == 0) return tmp * tmp;
    else return x * tmp * tmp;
}


std::string value_to_str(double value) {
    const double fault = 0.001;
    for (size_t i = 0; i < gearbox_values.size(); i++) {
        if (std::fabs(value - gearbox_values[i]) < fault) {
            return gearbox_strings[i];
        }
    }
    return "unknown";
}

std::pair<std::vector<double>, double> find_nearest_gearbox(double target_value, size_t gearbox_count) {
    std::vector<double> closest_combination;
    double closest_product = 0.0;
    double min_difference = std::numeric_limits<double>::max();

    std::vector<double> combination(gearbox_count, 1);
    size_t total_combinations = myPow(gearbox_values.size(), gearbox_count);

    for (size_t i = 0; i < total_combinations; ++i) {
        size_t index = i;
        for (int j = 0; j < gearbox_count; ++j) {
            combination[j] = gearbox_values[index % gearbox_values.size()];
            index /= gearbox_values.size();
        }

        double product = 1.0;
        for (const auto& value : combination) {
            product *= value;
        }

        double difference = std::fabs(product - target_value);

        if (difference < min_difference) {
            min_difference = difference;
            closest_combination = combination;
            closest_product = product;
        }
    }

    return { closest_combination, closest_product };
}

int main(int argc, char** argv) {
    double target_value;
    size_t gearbox_count;
    bool interactive = false;
    if (argc >= 3) {
        target_value = std::atof(argv[1]);
        gearbox_count = std::atoi(argv[2]);
    }
    else
    {
        interactive = true;
        std::cout << "target_value: ";
        std::cin >> target_value;
        std::cout << "gearbox_count: ";
        std::cin >> gearbox_count;
        std::cout.put('\n');
    }

    auto [closest_combination, closest_product] = find_nearest_gearbox(target_value, gearbox_count);

    std::cout << "Closest combination: ";
    for (const auto& value : closest_combination) {
        std::cout << value_to_str(value) << " ";
    }
    std::cout << "\nClosest product: " << closest_product << std::endl;
    if (interactive) {
        system("pause");
    }
    return 0;
}