Editing 3274 - secvb (section)

=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3274 - secvb

def count_set_bits(num):
    # Funcție care numără biții de 1 în reprezentarea binară a unui număr
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count


def find_sequences(N, T, seq):
    # Funcție care găsește numărul de secvențe cu proprietatea B(i, j) = T
    count = 0
    prefix_sums = [0] * (N + 1)  # Prefixe de sume pentru a putea calcula B(i, j) în O(1)

    # Calculăm prefixele de sume ale numărului de biți de 1 din secvență
    for i in range(1, N + 1):
        prefix_sums[i] = prefix_sums[i - 1] + count_set_bits(seq[i - 1])

    # Parcurgem toate perechile (i, j) și numărăm secvențele care satisfac proprietatea
    for i in range(1, N + 1):
        for j in range(i, N + 1):
            if prefix_sums[j] - prefix_sums[i - 1] == T:
                count += 1

    return count


def validate_input(N, T, seq):
    # Funcție care validează datele de intrare
    if not (1 <= N <= 50000):
        return False
    if not (0 <= T <= 100000):
        return False
    if not all(1 <= x <= 1000 for x in seq):
        return False
    return True


if __name__ == "__main__":
    # Citirea datelor de intrare
    with open("secvb.in", "r") as file:
        N, T = map(int, file.readline().split())
        seq = list(map(int, file.readline().split()))

    # Validarea datelor de intrare
    if not validate_input(N, T, seq):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")

        # Rezolvarea problemei și afișarea rezultatului
        result = find_sequences(N, T, seq)
        print(result)

        # Scrierea rezultatului în fișierul de ieșire
        with open("secvb.out", "w") as file:
            file.write(str(result))


</syntaxhighlight>