3274 - secvb

Sursa: 3274 - secvb

Pentru un număr natural x, vom nota cu B(x) numărul biților de 1 din reprezentarea lui x în baza 2. De exemplu, B(6) = 2, B(15) = 4, B(16) = 1. Fie un șir de N numere naturale x1, x2, …, xN. Pentru orice două valori i și j, cu 1 ≤ i ≤ j ≤ N, vom nota prin B(i, j) = B(xi) + B(xi+1) + ... + B(xj), adică B(i, j) este numărul tuturor biților de 1 din secvența de numere xi, xi+1, …, xj.

Cerinţa

Dat șirul x1, x2, …, xN și un număr natural T, să se determine numărul secvențelor de forma xi, xi+1, …, xj cu proprietatea că B(i,j) = T.

Date de intrare

Fișierul de intrare secvb.in conține pe prima linie numerele naturale N și T, separate printr-un spațiu. Pe linia a doua se găsesc N numere naturale x1, x2, …, xN separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire secvb.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou prima linie numerele naturale N și T, separate printr-un spațiu. Pe linia a doua se găsesc N numere naturale x1, x2, …, xN separate prin câte un spațiu., reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ N ≤ 50.000
0 ≤ T ≤ 100.000
valorile din şir sunt numere naturale cuprinse între 1 și 1000.

Exemplu 1

Intrare: secvb.in; 7 6; 8 3 7 14 10 63 1
Ieșire: Datele sunt introduse correct.; secvb.out; 3

Exemplu 2

Intrare: secvb.in; 23 - 2 -3 41; 99 0 7 5 23 59 1
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

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>

Explicatie Rezolvare

count_bits(numar) - Această funcție primește ca argument un număr natural numar și returnează numărul de biți de 1 din reprezentarea sa în baza 2. Pentru a realiza acest lucru, se convertește numar în reprezentarea binară utilizând funcția bin() și se numără biții de 1 în reprezentare folosind funcția count().

find_sequences(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția parcurge toate posibilele secvențe de elemente din lista și verifică dacă suma biților de 1 din secvență este egală cu T. Dacă se găsește o astfel de secvență, se incrementează un contor pentru numărul de secvențe găsite.

validate_input(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția validează dacă datele de intrare corespund restricțiilor impuse în enunțul problemei. Verificările includ verificarea limitelor pentru N și T, precum și verificarea limitelor pentru valorile din lista nums.

read_input() - Această funcție este responsabilă de citirea datelor de intrare din fișierul "secvb.in". Ea returnează valorile citite pentru N, T și lista nums.

write_output(result) - Această funcție primește rezultatul obținut și este responsabilă de scrierea rezultatului în fișierul "secvb.out" conform formatului specificat în cerințe.

Blocul if __name__ == "__main__": - Acesta este blocul principal al codului și se execută doar atunci când fișierul este rulat direct (nu este importat ca modul în alt script). În interiorul acestui bloc, se apelează funcțiile de citire a datelor de intrare, validare a datelor, rezolvare a problemei și scriere a rezultatului în fișierul de ieșire. Dacă datele de intrare sunt introduse corect, se afișează mesajul "Datele sunt introduse corect." în consolă.