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