hdu 1041 Computer Transformation

Computer Transformation

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

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 #include <iostream>
 4 using namespace std;
 5 int ans[1000][100];
 6 int main()
 7 {
 8     int n;
 9     memset(ans,0,sizeof(ans));
10     for(int i=2; i<=1000; i++)
11     {
12         for(int j=0; j<100; j++)
13             ans[i][j]=ans[i-1][j];
14         int t=0;
15         if(i&1)
16         {
17             for(int j=0; j<100; j++)
18             {
19                 t=t+ans[i][j]*2;
20                 ans[i][j]=t%1000000;
21                 t/=1000000;
22             }
23             ans[i][0]-=1;
24         }
25         else
26         {
27             for(int j=0; j<100; j++)
28             {
29                 t=t+ans[i][j]*2;
30                 ans[i][j]=t%1000000;
31                 t/=1000000;
32             }
33             ans[i][0]+=1;
34         }
35     }
36     while(scanf("%d",&n)!=EOF)
37     {
38         int k=99;
39         if(n==1)
40         {
41             puts("0");
42             continue;
43         }
44         while(ans[n][k]==0) k--;
45         printf("%d",ans[n][k]);
46         k--;
47         for(int j=k; j>=0; j--)
48             printf("%06d",ans[n][j]);
49         putchar(10);
50     }
51     return 0;
52 }

View Code