hdu_1041_Computer Transformation_201311051648

Computer Transformation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5065 Accepted Submission(s): 1850

Problem Description

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.
How many pairs of consequitive zeroes will appear in the sequence after n steps?

Input

Every input line contains one natural number n (0 < n ≤1000).

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample Input

2

3

Sample Output

1

1

Source

Southeastern Europe 2005

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int an1[500],an2[500];
 5 char s[1010][500];
 6 
 7 int main()
 8 {
 9     int i,j,k,len,t,n,aa;
10     memset(an1,0,sizeof(an1));
11     memset(an2,0,sizeof(an2));
12     memset(s,0,sizeof(s));
13     strcpy(s[1],"0");
14     strcpy(s[2],"1");
15     an1[0]=1;
16     len=0;t=0;
17     for(i=3;i<=1000;i++)
18     {
19         t=0;
20         for(j=0;j<=len;j++)
21         {
22             an2[j]=an1[j]*2+t;
23             if(an2[j]>9)
24             {
25                 an2[j]-=10;
26                 t=1;
27             }
28             else
29             t=0;
30             if(j==len&&t==1)
31             len+=1;
32             an1[j]=an2[j];
33         }
34         if(i&1)
35         {an1[0]=an2[0]-=1;}
36         else
37         {an1[0]=an2[0]+=1;}
38         for(k=0,aa=j-1;aa>=0;aa--)
39         {
40             an1[aa]=an2[aa];
41             s[i][k++]=an2[aa]+'0';
42         }            
43     }
44     while(scanf("%d",&n)!=EOF)
45     {
46         printf("%s
",s[n]);
47     }
48     return 0;
49 }
50 //大数，找规律

找规律，大数问题