// Tiempo y espacio de la recursión de TQBF con una familia de fórmulas verdaderas:
//
//     ∀x1 ∃y1 ∀x2 ∃y2 … ∀xk ∃yk  ((x1 ∨ y1) ∧ (¬x1 ∨ ¬y1) ∧ … ∧ (xk ∨ yk) ∧ (¬xk ∨ ¬yk))
//
// Cada par de cláusulas dice que yi es distinta de xi. Las llamadas crecen exponencialmente
// con k; las llamadas activas a la vez, linealmente.
#include <cstdio>
#include <string>

#include "qbf.h"

static Qbf different_pairs(int k) {
    Qbf f;
    for (int i = 1; i <= k; i++) {
        f.variables.push_back("x" + std::to_string(i));
        f.quantifiers.push_back('A');
        f.variables.push_back("y" + std::to_string(i));
        f.quantifiers.push_back('E');
        f.clauses.push_back({2 * i - 1, 2 * i});
        f.clauses.push_back({-(2 * i - 1), -(2 * i)});
    }
    return f;
}

int main() {
    std::printf("%s\n\n", to_text(different_pairs(2)).c_str());
    std::printf(" k   variables   valor       llamadas   activas a la vez\n");
    for (int k = 1; k <= 12; k++) {
        Qbf f = different_pairs(k);
        EvalStats stats;
        bool value = is_true(f, stats);
        std::printf("%2d   %9d   %-9s %10lld   %16d\n", k, 2 * k, value ? "verdadero" : "falso", stats.calls,
                    stats.max_depth);
    }
    return 0;
}
