// Cuenta las vueltas de los patrones de ciclos de los apuntes.
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

long long two_in_sequence(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        count++;
    }
    for (long long i = 0; i < n; i++) {
        count++;
    }
    return count;
}

long long nested_full(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

long long nested_triangle(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < i; j++) {
            count++;
        }
    }
    return count;
}

long long halving(long long n) {
    long long count = 0;
    for (long long j = n; j > 0; j /= 2) {
        count++;
    }
    return count;
}

long long nested_halving(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = i; j > 0; j /= 2) {
            count++;
        }
    }
    return count;
}

struct Pattern {
    std::string name;
    long long (*fn)(long long);
};

int main() {
    const std::vector<Pattern> patterns = {
        {"secuencia", two_in_sequence},
        {"anidados", nested_full},
        {"triangulo", nested_triangle},
        {"divide", halving},
        {"triangulo_divide", nested_halving},
    };
    const long long sizes[] = {1000, 2000, 4000, 8000};

    assert(two_in_sequence(1000) == 2 * 1000);
    assert(nested_full(1000) == 1000 * 1000);
    assert(nested_triangle(1000) == 1000 * 999 / 2);
    assert(halving(1024) == 11);

    std::printf("%-18s %10s %10s %10s %10s %7s\n", "patron", "n=1000", "n=2000", "n=4000", "n=8000",
                "razon");
    for (const Pattern& pattern : patterns) {
        std::printf("%-18s", pattern.name.c_str());
        long long previous = 0;
        long long last = 0;
        for (long long n : sizes) {
            previous = last;
            last = pattern.fn(n);
            std::printf(" %10lld", last);
        }
        std::printf(" %7.2f\n", static_cast<double>(last) / static_cast<double>(previous));
    }
    return 0;
}