Escribiendo paréntesis P82409


Statement
 

pdf   zip

html

Los Milabs son los habitantes del planeta Milab. Estos bichos tienen un cerebro altamente desarrollado. Por contra, sus prehistóricas cuerdas vocales están muy limitadas, cosa que les obligó a desarrollar el curioso lenguaje Nuxaeron.

El alfabeto del Nuxaeron es binario. Sin embargo, en vez de escribir con ceros y unos, (como todo buen programador haría) escriben con paréntesis. En principio, se pueden formar 2k palabras de longitud k, puesto que cada carácter puede ser ‘(’ (pronúnciese “uhng”) o bien ‘)’ (pronúnciese “uhhhn”). Pero aunque sean tan inteligentes, los Milabs son tan vagos como los habitantes de la Tierra, (o “()()(()(()))”, como ellos la llaman) y no quieren memorizar demasiadas palabras distintas. Por lo tanto, han establecido una norma: sólo pueden decir palabras bien parentizadas, o sea, pueden decir “()” o “(()())”, pero no pueden decir “())(” ni “)(”. Por ejemplo, éstas son las 5 palabras correctas de longitud 6:

((()))    ()(())    (())()    (()())    ()()()

Para hablar bien Nuxaeron, deberéis determinar cuantas palabras correctas de longitud n existen.

Entrada

La entrada consiste en diversos naturales n entre 1 y 67.

Salida

Para cada n, escribid la cantidad de palabras correctas en Nuxaeron de ese tamaño.

Observación

Si no conocéis qué son los números de Catalan, éste es un buen momento para aprenderlo.

Public test cases
  • Input

    1
    2
    3
    4
    6
    8
    

    Output

    0
    1
    0
    2
    5
    14
    
  • Input

    28
    66
    

    Output

    2674440
    212336130412243110
    
  • Information
    Author
    Enric Sánchez Cusell
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C C++