e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Проста задачка Шарика

prb1281 Ще задовго до того, як Шарик знайшов розумну книжку, загублену Пєчкіним, коли він лише розпочинав свої експерименти з розпилювання шахових дошок, коли ще на шаховій дошці білі поля були білими, а чорні – чорними, він задав одну зі своїх перших задачок Матроскіну.

"_Скільки різних послідовностей довжини n можна скласти з клітинок розпилених шахових дошок, якщо в жодній із послідованостей ніякі три білих поля не повинні йти підряд_"?

Матроскін так і не розв'язав ще цю задачку, так что ваше завдання допомогти йому.

Вхідні дані

Довжина послідовності n (n64).

Вихідні дані

Вивести кількість вказаних послідовностей.

Ліміт часу 1 секунд
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1
Вихідні дані #1
2
Вхідні дані #2
2
Вихідні дані #2
4
Вхідні дані #3
3
Вихідні дані #3
7