2846. 统计字符串个数

单点时限: 2.0 sec

内存限制: 256 MB

在 0 和 1 组成的长度为 $n\ (1 \leqslant n \leqslant 20)$ 的字符串中,输出不包含 “101”子串的字符串的个数。

输入格式

本题有多组测试数据。每组测试数据占一行,含一个正整数 $n$,表示字符串的长度。n = -1 表示输入结束。

输出格式

对每组测试数据,在一行中输出表示不包含 “101”子串的字符串的个数。

样例

Input
3
4
10
20
-1
Output
7
12
351
97229

提示

长度为4,不包含“101”子串的字符串有12个:

$0000,0001,0010,0011$
$0100,0110,0111,1000$
$1001,1100,1110,1111$

1490 人解决,1604 人已尝试。

2094 份提交通过,共有 3650 份提交。

0.3 EMB 奖励。

创建: 13 年,10 月前.

修改: 6 年,1 月前.

最后提交: 3 周,4 天前.

来源: 编程实践第2次考试

题目标签