Rezolvare completă PbInfo #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.

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema secvb:

#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 ;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3274 secvb

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3274 secvb de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!