Costruire una scalinata
Data la disponibilità di
n mattoncini, si desidera costruire una scalinata impilandoli in colonne adiacenti. Poiché si tratta di una scalinata, non possono esserci due colonne della stessa altezza. Le colonne più a destra devono sempre essere più alte di quelle a sinistra. Avendo a disposizione questi n mattoncini, si vuole determinare in quanti modi diversi sia possibile costruire una scalinata valida.Input
L’input contiene un singolo intero
n (5 ≤ n ≤ 500).Output
Il programma deve stampare il numero di diverse scalinate che si possono ottenere a partire da quei mattoncini.
Esempi
Input | Output |
5 | 2 |
11 | 11 |
212 | 995645335 |
Spiegazione
- 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