Број партиција
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,1 s | 64 Mb | стандардни излаз | стандардни улаз |
Партиција позитивног природног броја \(n\) је растављање броја \(n\) на збир неколико позитивних природних бројева при чему је редослед сабирака небитан (стога можемо претпоставити да је тај редослед или увек нерастући или увек неопадајући). На пример, ако је редослед нерастући, партиције броја \(4\) су \(1+1+1+1\), \(2+1+1\), \(2+2\), \(3+1\), \(4\). Написати програм који одређује број партиција за дати природан број \(n\).
Улаз
Прва и једина линија стандардног улаза садржи природан број \(n\) (\(n \leq 100\)).
Излаз
На стандардном излазу приказати у првој линији број партиција природног броја \(n\).
Пример 1
Улаз
6
Излаз
11
Објашњење
Ако су партиције са неопадајуће сортираним сабирцима, то су партиције:
1+1+1+1+1+1 1+1+1+1+2 1+1+1+3 1+1+2+2 1+1+4 1+2+3 1+5 2+2+2 2+4 3+3 6
Пример 2
Улаз
100
Излаз
190569292
Морате бити улоговани како бисте послали задатак на евалуацију.