Construire un escalier
Étant donné
n briques, vous souhaitez construire un escalier en empilant ces briques dans des colonnes voisines. Comme il s’agit d’un escalier, il ne peut pas y avoir deux colonnes de la même hauteur. Les colonnes situées plus à droite doivent toujours être plus hautes que celles de gauche. Étant donné ces n briques, vous voudriez savoir combien de façons différentes il existe de construire un escalier valide.Entrée
L’entrée se compose d’un unique entier
n (5 ≤ n ≤ 500).Sortie
Le programme doit afficher le nombre de différents escaliers que l’on peut construire à partir de ces briques.
Exemples
Entrée | Sortie |
5 | 2 |
11 | 11 |
212 | 995645335 |
Explication
- n = 5
ㅤ | x |
x | x |
x | x |
ㅤ | x |
ㅤ | x |
ㅤ | x |
x | x |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB