// Costo de la programación dinámica O(nW) en instancias que salen de la reducción. Cada arista agrega un
// dígito en base 4, y el objetivo se multiplica por 4. Se compila con -O2, sin sanitizers.
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include "subset_sum.h"

namespace {

int bit_length(Number x) {
    int bits = 0;
    while (x > 0) {
        bits++;
        x >>= 1;
    }
    return bits;
}

}  // namespace

int main() {
    std::cout << " aristas   n   bits del objetivo    objetivo W             n·W   entrada en bits   respuesta   segundos\n";
    for (int edges = 2; edges <= 13; edges++) {
        // Un ciclo con tantas aristas como nodos. La cobertura mínima de un ciclo es ⌈E / 2⌉.
        Graph g(static_cast<std::size_t>(edges < 3 ? 3 : edges));
        for (int i = 0; i < edges; i++) {
            if (edges < 3) add_edge(g, i, i + 1);
            else add_edge(g, i, (i + 1) % edges);
        }
        int k = edges < 3 ? 1 : (edges + 1) / 2;
        SubsetSumInstance s = reduce_to_subset_sum(g, k);
        std::size_t input_bits = 0;
        for (Number x : s.numbers) input_bits += static_cast<std::size_t>(bit_length(x));
        input_bits += static_cast<std::size_t>(bit_length(s.target));
        auto start = std::chrono::steady_clock::now();
        bool answer = subset_sum_dp(s.numbers, s.target);
        std::chrono::duration<double> seconds = std::chrono::steady_clock::now() - start;
        std::cout << std::setw(8) << edges << std::setw(4) << s.numbers.size() << std::setw(20) << bit_length(s.target)
                  << std::setw(14) << s.target << std::setw(16) << static_cast<Number>(s.numbers.size()) * s.target
                  << std::setw(18) << input_bits << std::setw(12) << (answer ? "sí" : "no") << std::setw(11)
                  << std::fixed << std::setprecision(3) << seconds.count() << '\n';
    }
}