Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Старик Хоттабыч заметил, что в последнее время его заклинания часто работают неправильно, и решил повысить устойчивость заклинаний к случайным ошибкам. Для этого он поставил в соответствие каждому магическому действию комбинацию вырываемых волос из бороды. Например, комбинация белый волос + серый волос (БС) вызывает дождь, а комбинация серый волос + белый волос (СБ) – солнце. Т.к. у Хоттабыча мало серых волос в бороде, он решил никогда не вырывать их подряд.
Напишите программу, которая определяет количество всех возможных заклинаний, которые можно закодировать не более чем N волосами (N <= 20).
Входные данные:
Натуральное число N: количество волос
Выходные данные:
Количество заклинаний, которое закодировать не более чем N волосами.
Примеры:
Входные данные: 1
Выходные данные: 2
Входные данные: 2
Выходные данные: 5
Входные данные: 3
Выходные данные: 10
Для отправки решений необходимо выполнить вход.
|