Construindo uma escada
Dado
n tijolos, pretende construir uma escada empilhando esses tijolos em colunas adjacentes. Por se tratar de uma escada, não podem existir duas colunas com a mesma altura. As colunas à direita devem ser sempre mais altas do que as da esquerda. Tendo esses n tijolos, o objetivo é determinar de quantas maneiras diferentes se pode formar uma escada válida.Entrada
A entrada contém um único inteiro
n (5 ≤ n ≤ 500).Saída
O programa deve imprimir o número de diferentes escadas que podem ser construídas com esses tijolos.
Exemplos
Entrada | Saída |
5 | 2 |
11 | 11 |
212 | 995645335 |
Explicação
- 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