问题 E: 【提高】圣诞礼物gift

问题 E: 【提高】圣诞礼物gift

题目描述

  清晨,大地穿上了薄薄的白棉袄,小T一路哼着歌踏着雪来到了学校,哇:一棵五彩缤纷的圣诞树顿时映入眼帘!树上彩带迎风飘扬,校园里人流如潮,同学们一个个伸长了手在喊:“我要,我要!”咦?他们在干什么?小T奋力挤了进去,发现是一位穿着节日盛装的圣诞老人被大家围在中间,只见圣诞老人戴着可爱的红帽子,背着一个鼓鼓囊囊的大礼包正准备发礼物呢!小T见圣诞老人都快被大家挤得喘不过气来了,就立刻上前维持秩序,他将现场的同学排成一排等待圣诞老人发放礼物。圣诞老人的礼物有两种,一种是苹果,另一种是磁铁。由于磁铁之间有磁力,两个相邻的同学如果拿到的都是磁铁,他们就会被吸在一起而无法分开,苹果则不存在这个问题。圣诞老人想给这一排N个同学每人发一件礼物,同时又要避免相邻两个同学都拿到磁铁的情况,请问他有多少种发放礼物的方案? 你可以认为圣诞老人的大礼包中有足够多的苹果和足够多的磁铁,不会发生某种礼物发到后来不够用的情况。

输入

仅有一行包含一个自然数N,表示共有N个同学。

输出

仅有一行包含一个自然数,表示圣诞老人发放礼物的方案数。

样例输入输出

输入#1 复制
5
输出#1 复制
13

提示

【样例解释】
假设第i个数字为0表示第i个同学拿到的礼物是苹果,第i个数字为1表示第i个同学拿到的礼物是磁铁,则满足条件的全部方案如下所示:
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101
【数据范围】
80%的数据满足:N≤20 100%的数据满足:N≤40

序号 标题 作者 发表时间 费用 订购数 操作