# PBinfo #3274 – secvb – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

Exemplul 1:
secvb.in

7 6
8 3 7 14 10 63 1
secvb.out

3
Explicație
Sunt trei secvențe având în total 6 biți de 1:
8 3 7
7 14
63

Exemplul 2:
secvb.in

4 1
3 5 7 6
secvb.out

0
Explicație
Nu există nicio secvență pentru care suma biților de 1 să fie egală cu 1.

## Cod sursă C++

```cpp
#include<fstream>
#define InFile "secvb.in" 
#define OutFile "secvb.out" 
using namespace std ;
int N, T ;
int a[50001] ; // in a[i] se memoreaza pentru fiecare x[i] numarul bitilor de 1
int main()
{
	int i, k, x, st, dr, s;
	ifstream fin(InFile);
	fin >> N >> T ;
	for (i = 0 ; i < N; i++)
	{
		fin >> x;
		k = 0;
		while (x > 0)
		{
			k += (x % 2);
			x /= 2 ;
		}
		a[i] = k ;
	}
	fin.close() ;
	s = k = st = dr = 0;
	for (dr=0 ; dr<N ; dr++)
	{
		s += a[dr] ;
		while (s >= T)
		{	
			if (s == T) k++;
			s -= a[st];
			st++;
		}
	}
	ofstream fout(OutFile) ;
	fout << k << "\n" ;
	fout.close();
	return 0 ;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3274)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3274/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3274/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)