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 un singur număr natural reprezentând numărul de secvențe din șir care au numărul biților de 1 egal cu T.

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

Intrare: 7 6; 8 3 7 14 10 63 1
Ieșire: 3

Rezolvare

Rezolvare ver. 1

3274 - secvb

def read_input():

   n, t = map(int, input().split())
   x = list(map(int, input().split()))
   return n, t, x

def count_bits(x):

   cnt = 0
   while x:
       cnt += x & 1
       x >>= 1
   return cnt

def solve(n, t, x):

   cnt = 0
   for i in range(n):
       bits = count_bits(x[i])
       if bits == t:
           cnt += 1
       for j in range(i+1, n):
           bits += count_bits(x[j])
           if bits == t:
               cnt += 1
           if bits > t:
               break
   return cnt

def validate(n, t, x):

   cnt = 0
   for i in range(n):
       bits = count_bits(x[i])
       if bits == t:
           cnt += 1
       for j in range(i+1, n):
           bits += count_bits(x[j])
           if bits == t:
               cnt += 1
           if bits > t:
               break
   return cnt

if __name__ == '__main__':

   n, t, x = read_input()
   result = solve(n, t, x)
   print(result)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input citește datele de intrare și le returnează sub formă de tuplu. Funcția count_bits calculează numărul de biți de 1 din reprezentarea în baza 2 a unui număr dat. Funcția solve parcurge toate subsecvențele posibile din șir și calculează B(i,j) pentru fiecare subsecvență. Dacă B(i,j) este egal cu T, se incrementează contorul. Se returnează valoarea contorului. Funcția validate este identică cu funcția solve. In structura if __name__ == '__main__': apelăm funcția read_input pentru a obține datele de intrare, apoi apelăm funcția solve pentru a rezolva problema și afișăm rezultatul.