Expressions correctes P68813


Statement
 

pdf   zip

thehtml

En aquest problema considerem les expressions definides de la manera següent:

  • Tota variable és una expressió correcta;
  • si x és una expressió correcta, (x) també ho és;
  • si x1 i x2 són expressions correctes, (x1) − (x2) també ho és;
  • res més no és una expressió correcta.

Per exemple, si el conjunt de variables és A, B, C, algunes expressions correctes serien:

A    (A)    ((C))    (A)−(B)    ((A)−(B))−(A)

Feu un programa que, donats dos nombres n i m, escrigui el nombre d’expressions correctes de longitut exactament n que es poden construir amb m variables.

Per exemple, per a n =7 i m=2 el resultat hauria de ser 6, que es correspon a

(((A)))    (((B)))    (A)−(A)    (A)−(B)    (B)−(A)    (B)−(B)

Entrada

L’entrada consisteix en diversos casos, cadascun amb dos naturals n i m entre 1 i 25.

Sortida

Per a cada cas, escriviu el nombre d’expressions correctes de longitut exactament n que es poden construir amb m variables. Aquest nombre sempre serà inferior a 109.

Public test cases
  • Input

    7 2
    1 20
    20 1
    21 1
    25 25
    

    Output

    6
    20
    0
    212
    307378150
    
  • Information
    Author
    Omer Giménez
    Language
    Catalan
    Other languages
    English Spanish
    Official solutions
    C++
    User solutions
    C++ Python