3485：Count 101

题目描述

You know YaoYao is fond of his chains. He has a lot of chains and each chain has n diamonds on it. There are two kinds of diamonds, labeled 0 and 1. We can write down the label of diamonds on a chain. So each chain can be written as a sequence consisting of 0 and 1.
We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring.
Could you tell how many chains will YaoYao have at most?

输入解释

There will be multiple test cases in a test data. For each test case, there is only one number n(n<10000). The end of the input is indicated by a -1, which should not be processed as a case.

输出解释

For each test case, only one line with a number indicating the total number of chains YaoYao can have at most of length n. The answer should be print after module 9997.

输入样例

3
4
-1

输出样例

7
12

提示

We can see when the length equals to 4. We can have those chains:
0000,0001,0010,0011
0100,0110,0111,1000
1001,1100,1110,1111

来自杭电HDUOJ的附加信息

Recommend

zhengfeng

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU

源链接： HDU-3485

最后修改于 2020-10-25T23:04:02+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	65536/32768K(Java/Others)