Count 101Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 187 Accepted Submission(s): 73 Problem Description 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? Input 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. Output 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. SampleInput 3 4 -1 SampleOutput 7 12 HintWe 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
#include<stdio.h>
int f[2][2];
int g[10010];
int main()
{
g[0]=0;
g[1]=2;
f[0][0]=1;
f[0][1]=1;
f[1][0]=1;
f[1][1]=1;
g[2]=4;
for(int i=3;i<10000;i++)
{
int t1=f[0][0];
int t2=f[0][1];
int t3=f[1][0];
int t4=f[1][1];
f[0][0]=(t1+t3)%9997;
f[0][1]=t1%9997;
f[1][0]=(t2+t4)%9997;
f[1][1]=(t2+t4)%9997;
g[i]=(f[0][0]+f[0][1]+f[1][0]+f[1][1])%9997;
}
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==-1) break;
if(n==0) printf("0/n");
printf("%d/n",g[n]);
}
return 0;
}