// Tabla de crecimiento, y el mayor n que cabe en un presupuesto de operaciones.
#include <cmath>
#include <cstdio>
#include <initializer_list>

using Cost = double (*)(double);

double cost_log(double n) { return std::log2(n); }
double cost_linear(double n) { return n; }
double cost_n_log(double n) { return n * std::log2(n); }
double cost_square(double n) { return n * n; }
double cost_cube(double n) { return n * n * n; }
double cost_exp(double n) { return std::pow(2.0, n); }

// El mayor entero n, desde 2, con cost(n) <= budget. Búsqueda binaria.
long long largest_n(Cost cost, double budget) {
    long long low = 2;
    long long high = 4;
    while (cost(static_cast<double>(high)) <= budget) {
        high *= 2;
    }
    while (high - low > 1) {
        long long middle = low + (high - low) / 2;
        if (cost(static_cast<double>(middle)) <= budget) {
            low = middle;
        } else {
            high = middle;
        }
    }
    return low;
}

int main() {
    std::printf("%8s %8s %10s %10s %10s %10s\n", "n", "log2 n", "n", "n log2 n", "n^2", "2^n");
    for (double n : {10.0, 20.0, 40.0, 80.0, 1000.0, 1000000.0}) {
        std::printf("%8.0f %8.1f %10.3g %10.3g %10.3g %10.3g\n", n, cost_log(n), n, cost_n_log(n),
                    cost_square(n), cost_exp(n));
    }

    const double budget = 1e9;
    std::printf("\ncon %.0f operaciones\n", budget);
    std::printf("%10s %14lld\n", "n", largest_n(cost_linear, budget));
    std::printf("%10s %14lld\n", "n log2 n", largest_n(cost_n_log, budget));
    std::printf("%10s %14lld\n", "n^2", largest_n(cost_square, budget));
    std::printf("%10s %14lld\n", "n^3", largest_n(cost_cube, budget));
    std::printf("%10s %14lld\n", "2^n", largest_n(cost_exp, budget));
    return 0;
}