h2(#biti3). 'Biti3':problema/biti3

Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j > i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.

Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j > i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i-1, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.

Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$}), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul: