// Dos algoritmos de streaming: leen los datos una sola vez, símbolo por símbolo, y al final
// responden. Toda su memoria está a la vista, para poder contar sus bits.
#ifndef STREAMING_H
#define STREAMING_H

#include <cstdint>

// ¿El k-ésimo símbolo desde el final es 1? Guarda los últimos k bits en un registro: k bits
// de memoria, ni uno más. La cota inferior de los apuntes dice que tampoco puede ser uno menos.
struct Window {
    int k = 1;                  // parámetro del problema, no cuenta como memoria (1 ≤ k ≤ 32)
    std::uint32_t bits = 0;     // los últimos k símbolos; el más reciente es el bit 0

    void read(char a) {
        std::uint32_t mask = (k == 32) ? 0xffffffffu : ((1u << k) - 1u);
        bits = ((bits << 1) | (a == '1' ? 1u : 0u)) & mask;
    }
    bool answer() const {
        return ((bits >> (k - 1)) & 1u) != 0;
    }
};

// ¿Hubo tantos ceros como unos? Guarda la diferencia. Con entradas de longitud a lo sumo n,
// la diferencia está entre -n y n: unos log2(2n + 1) bits. No hay un tope que sirva para toda n.
struct Balance {
    std::int64_t difference = 0;  // ceros menos unos

    void read(char a) {
        difference += (a == '0') ? 1 : -1;
    }
    bool answer() const {
        return difference == 0;
    }
};

#endif
