Flauta india P86839


Statement
 

pdf   zip

html

Walker no solo cultiva el cuerpo: también cultiva el espíritu. Para ello, nada mejor que relajarse tocando una melodía con su flauta india navaja. Esta flauta puede hacer sonar n notas distintas (desde la nota 0, hasta la nota n−1). Sin embargo, las reglas de composición melódica navajas son muy estrictas:

  • La primera nota de la melodía debe ser la nota 0.
  • La última nota de la melodía debe ser la nota n−1.
  • Cada nota tiene que ser exactamente la misma, una nota más o una nota menos que la anterior.
  • La misma nota no puede aparecer tres veces consecutivamente en la melodía.

Por ejemplo, las siguientes son melodías navajas de duración k=7 que pueden tocarse con una flauta india de n=4 notas:

0123233      0011233      0121123      0100123

Por contra, las siguientes melodías navajas no son válidas, puesto que incumplen los 4 principios anterioreS:

1233233      0123212      0013223      0122233

Se te pide que digas, dados los valores n y k, el número de melodías navajas distintas que Walker podría interpretar.

Entrada

La entrada contiene el número N de casos en una línea, seguido de N líneas con los números 1≤ n≤ 20 y 1≤ k≤ 30 de cada caso.

Salida

Escribe, para cada caso, el número de melodías navajas distintas de k notas de duración que es posible interpretar con una flauta india de n notas. Tu programa tiene 1 segundo de CPU para resolver cada entrada.

Puntuación

  • TestA:   Entradas con N≤ 20, n=1 y k≤ 10, como el Ejemplo 1.  15 Puntos 
  • TestB:   Entradas con N≤ 20, n ≤ 2 y k≤ 10, como el Ejemplo 2.  15 Puntos 
  • TestC:   Entradas con N≤ 20, n ≤ 4 y k≤ 10, como el Ejemplo 3.  15 Puntos 
  • TestD:   Entradas con N≤ 20, n ≤ 8 y k≤ 10, como el Ejemplo 4.  15 Puntos 
  • TestE:   Entradas con N≤ 100, n ≤ 10 y k≤ 20, como el Ejemplo 5.  15 Puntos 
  • TestF:   Entradas con N≤ 100, n ≤ 20 y k≤ 30, como el Ejemplo 6.  15 Puntos 
  • TestG:   Entradas con N≤ 10000, n ≤ 20 y k≤ 30.  10 Puntos 
Public test cases
  • Input

    2
    1 2
    1 10
    

    Output

    1
    0
    
  • Input

    4
    1 2
    2 2
    2 6
    2 10
    

    Output

    1
    1
    7
    44
    
  • Input

    3
    4 10
    3 10
    2 10
    

    Output

    290
    214
    44
    
  • Input

    2
    8 10
    6 10
    

    Output

    35
    174
    
  • Input

    2
    10 20
    5 20
    

    Output

    818528
    2108488
    
  • Input

    2
    20 30
    10 30
    

    Output

    64675289
    22397976711
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++