Eine Treppe bauen
Wenn du
n Bausteine zur Verfügung hast, möchtest du daraus eine Treppe errichten, indem du sie in benachbarten Spalten übereinander stapelst. Da es sich um eine Treppe handelt, dürfen keine zwei Spalten die gleiche Höhe haben. Die rechten Spalten müssen immer höher sein als die linken. Mithilfe dieser n Bausteine möchtest du herausfinden, auf wie viele verschiedene Arten sich eine gültige Treppe konstruieren lässt.Eingabe
Die Eingabe enthält eine einzelne ganze Zahl
n (5 ≤ n ≤ 500).Ausgabe
Das Programm soll die Anzahl aller möglichen unterschiedlichen Treppen ausgeben, die sich mit diesen Bausteinen bauen lassen.
Beispiele
Eingabe | Ausgabe |
5 | 2 |
11 | 11 |
212 | 995645335 |
Erklärung
- 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