Лестница
Вы поднимаетесь по лестнице, в которой всего
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