#include <iostream>
#include <memory>
#include <random>
#include <chrono>
#include <format>
#include <mutex>
#include <thread>

struct Number {
    std::string number;

    Number operator+(const int n) const {
        std::string ans;
        int carry = n;
        auto process = [&](char c) {
            int d = c - '0';
            d += carry;
            ans.push_back(d % 10 + '0');
            carry = d / 10;
        };
        for (char c : number)
            process(c);
        while (carry)
            process('0');
        return Number{.number = ans};
    }

    Number operator*(const int n) const {
        std::string ans;
        int carry = 0;
        auto process = [&](char c) {
            int d = c - '0';
            d *= n;
            d += carry;
            ans.push_back(d % 10 + '0');
            carry = d / 10;
        };
        for (char c : number)
            process(c);
        while (carry)
            process('0');
        return Number{.number = ans};
    }

    int operator%(const int n) const {
        int r = 0;
        for (auto it = number.rbegin(); it != number.rend(); ++it)
            r = (r * 10 + (*it - '0')) % n;
        return r;
    }

    Number operator/(const int n) const {
        std::string ans;
        int r = 0;
        for (auto it = number.rbegin(); it != number.rend(); ++it) {
            r = r * 10 + (*it - '0');
            if (r / n > 0 || !ans.empty())
                ans.push_back('0' + r / n);
            r %= n;
        }
        std::reverse(ans.begin(), ans.end());
        return Number{.number = ans};
    }

    bool operator<(const Number &other) const {
        if (number.size() != other.number.size())
            return number.size() < other.number.size();
        for (ssize_t i = ssize(number) - 1; i >= 0; --i)
            if (number[i] != other.number[i])
                return number[i] < other.number[i];
        return false;
    }

    template<class Int>
    static Number fromInt(const Int& n) {
        Number ans{
            .number = std::to_string(n),
        };
        std::reverse(ans.number.begin(), ans.number.end());
        return ans;
    }
};

std::ostream& operator<<(std::ostream& out, const Number& n) {
    if (n.number.empty())
        return out << '0';
    for (ssize_t i = ssize(n.number) - 1; i >= 0; --i)
        out << n.number[i];
    return out;
}

Number random_in_big_segment(const Number& left, const Number& right, auto& rng) {
    while (true) {
        Number ans;
        for (ssize_t i = 0; i < ssize(right.number); ++i)
            ans.number.push_back(std::uniform_int_distribution<int>('0', '9')(rng));
        while (!ans.number.empty() && ans.number.back() == '0')
            ans.number.pop_back();
        if (!(right < ans) && !(ans < left))
            return ans;
    }
}

struct Strategy {
    virtual bool choose_deterministic(const Number& n) const = 0;
    virtual std::string get_name() const = 0;
};

std::pair<double, double> test_strategy(std::shared_ptr<Strategy> strategy, const Number& n, const size_t tries, const size_t digit_limit) {
    double sum = 0;
    const Number ONE = Number::fromInt(1), TWO = Number::fromInt(2);
    std::vector<size_t> u;
    std::mutex m;
    std::vector<std::thread> threads;
    const size_t THREADS = std::thread::hardware_concurrency();
    bool tilt = false;
    for (size_t thread_index = 0; thread_index < THREADS; ++thread_index)
        threads.emplace_back([thread_index, &m, &ONE, &n, &sum, &u, &strategy, &tries, &THREADS, &digit_limit, &tilt, &TWO](){
            for (size_t i = thread_index; i < tries; i += THREADS) {
                std::mt19937 rng(i);
                Number a = random_in_big_segment(TWO, n, rng);
                size_t digits = 0;
                while (ONE < a && digits < digit_limit) {
                    bool choice = strategy->choose_deterministic(a);
                    if (choice) {
                        if (a % 2 == 0)
                            a = a / 2;
                        else
                            a = a * 3 + 1;
                    } else {
                        a = random_in_big_segment(a * 3 + 1, a * 6, rng);
                    }
                    digits += a.number.size();
                }
                std::lock_guard lock(m);
                if (digits >= digit_limit)
                    tilt = true;
                if (tilt)
                    break;
                sum += digits;
                u.push_back(digits);
            }
        });
    for (std::thread& thread : threads)
        thread.join();
    if (tilt)
        return {digit_limit, 0};
    double mean = sum / tries;
    double variance = 0;
    for (double op : u)
        variance += (op - mean) * (op - mean);
    double std = sqrt(variance) / (tries - 1);
    return {mean, std};
}

void test_strategies(std::vector<std::shared_ptr<Strategy>> strategies, const Number& n, const size_t tries, const size_t operation_limit) {
    for (auto strategy : strategies) {
        auto [mean, std] = test_strategy(strategy, n, tries, operation_limit);
        std::cout << std::format("{:%FT%TZ}: ", std::chrono::system_clock::now()) << strategy->get_name() << ": " << mean << " +- " << std << std::endl;
    }
}

size_t simple_kollatz_length(Number n, size_t max_tries) {
    size_t ans;
    const Number ONE = Number::fromInt(1);
    for (ans = 0; ans <= max_tries && ONE < n; ++ans) {
        ++ans;
        if (n % 2 == 0)
            n = n / 2;
        else
            n = n * 3 + 1;
    }
    return ans;
}

struct DeterministicStrategy : Strategy {
    bool choose_deterministic(const Number& n) const override {
        return true;
    }
    std::string get_name() const override {
        return "deterministic";
    }
};

struct LogStrategy : Strategy {
    double d;
    LogStrategy(const double d) : d(d) {
    }
    bool choose_deterministic(const Number& n) const override {
        std::string s = n.number + '.' + '0';
        std::reverse(s.begin(), s.end());
        double logarithm = (n.number.size() * log(10) + log(atof(s.c_str()))) * d;
        return simple_kollatz_length(n, floor(logarithm)) <= logarithm || logarithm >= 2000;
    }
    std::string get_name() const override {
        return std::format("logarithmic({:.3f})", d);
    }
};

int main(int argc, char* argv[]) {
    int u = 27;
    int it = 0;
    do {
        std::cout << u << " \\to ";
        if (u % 2 == 0) u /= 2;
        else u = u * 3 + 1;
        ++it;
    } while (u > 1);
    std::cout << u << '\n' << it << '\n';
    const double MIN_LOG_STRATEGY = atoi(argv[1]);
    const double MAX_LOG_STRATEGY = atoi(argv[2]);
    const int N_LOG_STRATEGIES = atoi(argv[3]);
    const int MAX_TESTED_NUM = atoi(argv[4]);
    const int TRIES = atoi(argv[5]);
    const int DIGIT_LIMIT = atoi(argv[6]);
    std::cerr << std::format("MIN_LOG_STRATEGY: {}\n", MIN_LOG_STRATEGY);
    std::cerr << std::format("MAX_LOG_STRATEGY: {}\n", MAX_LOG_STRATEGY);
    std::cerr << std::format("N_LOG_STRATEGIES: {}\n", N_LOG_STRATEGIES);
    std::cerr << std::format("MAX_TESTED_NUM: {}\n", MAX_TESTED_NUM);
    std::cerr << std::format("TRIES: {}\n", TRIES);
    std::cerr << std::format("OPERATION_LIMIT: {}\n", DIGIT_LIMIT);
    std::vector<std::shared_ptr<Strategy>> strategies{
        std::make_shared<DeterministicStrategy>(),
    };
    for (int i = 0; i < N_LOG_STRATEGIES; ++i)
        strategies.push_back(std::make_shared<LogStrategy>(MIN_LOG_STRATEGY + (MAX_LOG_STRATEGY - MIN_LOG_STRATEGY) * i / std::max(1, N_LOG_STRATEGIES - 1)));
    test_strategies(strategies, Number::fromInt(MAX_TESTED_NUM), TRIES, DIGIT_LIMIT);
    return 0;
}
