// El rojinegro válido con menos nodos para cada altura: qué tan cerca llega de la cota.
// Se calcula el camino más largo color por color; fuera del camino se cuelgan árboles
// todos negros, que son los que menos nodos gastan para una cantidad de negros dada.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <tuple>

namespace {

const long impossible = std::numeric_limits<long>::max() / 2;

long all_black(int blacks) { return (1L << blacks) - 1; }

// Quedan `nodes` nodos del camino y `blacks` negros por poner. Devuelve los nodos que hacen falta.
long cheapest(int nodes, int blacks, bool after_red, std::map<std::tuple<int, int, bool>, long>& known) {
    if (nodes == 0) {
        return blacks == 0 ? 0 : impossible;
    }
    if (blacks < 0 || blacks > nodes) {
        return impossible;
    }
    auto key = std::make_tuple(nodes, blacks, after_red);
    auto found = known.find(key);
    if (found != known.end()) {
        return found->second;
    }
    long best = impossible;
    if (blacks >= 1) {
        long below = cheapest(nodes - 1, blacks - 1, false, known);
        best = std::min(best, 1 + all_black(blacks - 1) + below);
    }
    if (!after_red) {
        long below = cheapest(nodes - 1, blacks, true, known);
        best = std::min(best, 1 + all_black(blacks) + below);
    }
    known[key] = best;
    return best;
}

// La raíz es negra.
long fewest_nodes(int height, int& blacks_used) {
    std::map<std::tuple<int, int, bool>, long> known;
    long best = impossible;
    for (int blacks = 1; blacks <= height + 1; blacks++) {
        long total = 1 + all_black(blacks - 1) + cheapest(height, blacks - 1, false, known);
        if (total < best) {
            best = total;
            blacks_used = blacks;
        }
    }
    return best;
}

}  // namespace

int main() {
    std::cout << std::setw(3) << "h" << std::setw(11) << "min.nodos" << std::setw(7) << "negros" << std::setw(9) << "cota"
              << std::setw(8) << "h/log2n" << "\n";
    for (int h : {0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 24, 32, 40}) {
        int blacks = 0;
        long n = fewest_nodes(h, blacks);
        double bound = 2 * std::log2(n + 1.0) - 1;
        std::cout << std::setw(3) << h << std::setw(11) << n << std::setw(7) << blacks << std::fixed << std::setprecision(2)
                  << std::setw(9) << bound << std::setw(8) << (n > 1 ? h / std::log2(static_cast<double>(n)) : 0.0) << "\n";
    }
    return 0;
}