Vectors harmoniosos P33354

Diem que un vector v de n bits és d-harmoniós per a un natural d si, per a cada i amb 0≤ i<n, la diferència (en valor absolut) entre el nombre de zeros i el nombre de uns en v[0,…,i] és inferior o igual a d.

Per exemple, hi ha 4 vectors 1-harmoniosos de llargada 4: 0101, 0110, 1001, i 1010. Igualment, hi ha 12 vectors 2-harmoniosos de llargada 4: 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100 i 1101. També, hi ha 4 vectors 1-harmoniosos de llargada 3: 010, 011, 100 i 101. Fixeu-vos que no hi ha vectors 0-harmoniosos per a n>0, però que n’hi ha un de llargada n=0 (el vector buit).

Escriviu un programa que, per a uns n i d donats escrigui quants vectors de mida n són d-harmoniosos.

Entrada

L’entrada consisteix en una seqüència de parells naturals n, d ≥ 0.

Sortida

Per a cada n i cada d, escriviu quants vectors de mida n són d-harmoniosos.