// Calcula las recurrencias con grupos de 5 y de 3, tal como salen de contar elementos, y compara T(n)/n.
//   T5(n) = T5(techo(n/5)) + T5(piso(7n/10) + 3) + n    para n >= 80
//   T3(n) = T3(techo(n/3)) + T3(piso(2n/3) + 2) + n     para n >= 80
// Con n < 80 se toma T(n) = n.
#include <cstdio>
#include <vector>

int main() {
    const long long limit = 10240000;
    std::vector<long long> t5(limit + 1);
    std::vector<long long> t3(limit + 1);
    for (long long n = 0; n <= limit; n++) {
        if (n < 80) {
            t5[n] = n;
            t3[n] = n;
        } else {
            t5[n] = t5[(n + 4) / 5] + t5[7 * n / 10 + 3] + n;
            t3[n] = t3[(n + 2) / 3] + t3[2 * n / 3 + 2] + n;
        }
    }
    std::printf("%10s %10s %10s\n", "n", "T5(n)/n", "T3(n)/n");
    for (long long n = 10000; n <= limit; n *= 4) {
        std::printf("%10lld %10.2f %10.2f\n", n,
                    static_cast<double>(t5[n]) / static_cast<double>(n),
                    static_cast<double>(t3[n]) / static_cast<double>(n));
    }
    double worst = 0;
    for (long long n = 1; n <= limit; n++) {
        double ratio = static_cast<double>(t5[n]) / static_cast<double>(n);
        if (ratio > worst) {
            worst = ratio;
        }
    }
    std::printf("mayor T5(n)/n con n hasta %lld: %.2f\n", limit, worst);
}