// Cuánto se reinserta en total si se duplica al superar α = 1, empezando con 8 casillas.
#include <cstddef>
#include <cstdio>
#include <initializer_list>

int main() {
    std::printf("%10s %10s %12s %12s\n", "n", "casillas", "reinsertadas", "por_insercion");
    for (std::size_t n : {1000u, 10000u, 100000u, 1000000u, 1048576u, 1048577u}) {
        std::size_t capacity = 8;
        std::size_t moved = 0;
        for (std::size_t size = 0; size < n; size++) {
            // Antes de insertar la clave número size + 1.
            if (size + 1 > capacity) {
                moved += size;
                capacity *= 2;
            }
        }
        std::printf("%10zu %10zu %12zu %12.2f\n", n, capacity, moved, static_cast<double>(moved) / static_cast<double>(n));
    }
}