Expresiones correctas P68813


Statement
 

pdf   zip

thehtml

En este problema consideramos las expresiones definidas de la manera siguiente:

  • Toda variable es una expresión correcta;
  • si x es una expresión correcta, (x) también lo es;
  • si x1 y x2 son expresiones correctas, (x1) − (x2) también lo es;
  • nada más es una expresión correcta.

Por ejemplo, si el conjunto de variables es A, B, C, éstas serían algunas expresiones correctas:

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

Haced un programa que, dados dos números n y m, escriba el número de expresiones correctas de longitud exactamente n que se pueden construir con m variables.

Por ejemplo, para n = 7 y m = 2 el resultado debería ser 6, correspondiente a

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

Entrada

La entrada consiste en diversos casos, cada uno con dos naturales n y m entre 1 y 25.

Salida

Para cada caso, escribid el número de expresiones correctas de longitud exactamente n que se pueden construir con m variables. Este número será siempre 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
    Spanish
    Translator
    Omer Giménez
    Original language
    Catalan
    Other languages
    Catalan English
    Official solutions
    C++
    User solutions
    C++ Python