Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Secvb

Adăugată de :
sorynsoo
Sursă :
XOR2011
Autor :
-
Grupă :
Mica
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
4096 kbytes

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, xi+2, ..., 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, xi+2, ..., xj cu proprietatea că B(i,j) = T.

 

Date de intrare

Fişierul de intrare 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 iesire

Fişierul de iesire 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

  Date de intrare

  Date de iesire

  Explicaţii

  7 6

  8 3 7 14 10 63 1

  3

  Sunt trei secvenţe având în total 6 biţi de 1:

  8 3 7

  7 14

  63

  Date de intrare

  Date de iesire

  Explicaţii

  4 1

  3 5 7 6

  0

  Nu există nicio secvenţă pentru care suma biţilor de 1 să fie egală cu 1


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !