Vectors harmoniosos P33354


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    4 1
    4 2
    3 1
    8 1
    8 2
    8 7
    8 8
    1000 0
    0 0
    0 1
    

    Output

    4
    12
    4
    16
    108
    254
    256
    0
    1
    1
    
  • Input

    5 0   5 1   5 2   5 3   5 4   5 5
    

    Output

    0
    8
    18
    28
    30
    32
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    C++ Python