Աստիճաններ
Դուք բարձրանում եք աստիճաններով, որտեղ կա
n աստիճան։ Յուրաքանչյուր քայլի դեպքում կարող եք բարձրանալ կամ 2 աստիճան, կամ միայն 1։ Քանի՞ տարբեր եղանակով կարելի է բարձրանալ այդ աստիճաններով:Մուտք
Մուտքը պարունակում է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 45):Ելք
Ելքում պետք է տպել այն տարբեր եղանակների քանակը, որոնցով կարելի է բարձրանալ տվյալ աստիճանները:
Օրինակներ
Մուտք | Ելք |
2 | 2 |
3 | 3 |
Պարզաբանում
- 2 աստիճանի դեպքում → (1) 1 քայլ + 1 քայլ, (2) 2 քայլ
- 3 աստիճանի դեպքում → (1) 1 քայլ + 1 քայլ + 1 քայլ, (2) 1 քայլ + 2 քայլ, (3) 2 քայլ + 1 քայլ
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB