ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1225. Флаги

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
  1. Полоски одного цвета не должны располагаться рядом друг с другом.
  2. Синяя полоска может быть расположена только между белой и красной или между красной и белой.
Определите количество способов выполнить желание владельца магазина.
Например, для N = 3 возможны следующие варианты:
Problem illustration

Исходные данные

N — количество полосок, 1 ≤ N ≤ 45.

Результат

M — количество способов украсить витрину.

Пример

исходные данныерезультат
3
4
Источник задачи: Четвертьфинальные соревнования ACM ICPC 2002–2003 в центральном регионе России, Рыбинск, октябрь 2002