// Cuántos niveles necesita un árbol con mil millones de claves, según las claves por nodo.
// Es el mejor caso: todos los nodos llenos. Con m claves por nodo, L niveles guardan (m + 1)^L - 1.
#include <iomanip>
#include <iostream>

int main() {
    const long long keys = 1000000000;
    std::cout << std::setw(16) << "claves.por.nodo" << std::setw(9) << "niveles" << "\n";
    for (long long per_node : {1LL, 3LL, 15LL, 100LL, 500LL, 1000LL}) {
        long long room = 0;
        int levels = 0;
        while (room < keys) {
            room = room * (per_node + 1) + per_node;
            levels++;
        }
        std::cout << std::setw(16) << per_node << std::setw(9) << levels << "\n";
    }
    return 0;
}