poj 2680 Computer Transformation----簡単なプッシュ

Computer Transformation
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 4120
 
Accepted: 1592
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 consequitive zeroes pairs that will appear in the sequence after n steps.
Sample Input

2
3

Sample Output

1
1

Source
Southeastern Europe 2005
 
始めの数字は1で、毎回1が01になって、0が10になって、n歩を経て、何対の連続する0があって、つまり何対の00を聞きます.
時計を打つと法則が発見されやすい.
高精を使う.
表を打つコード:

#include
#include
#include
#include
using namespace std;
int s1[1000];
int s2[1000];
int main()
{
    int i=0;
    memset(s1,-1,sizeof(s1));
    memset(s2,-1,sizeof(s2));
    s1[0]=1;
    while(i<10)
    {
        i++;
        int cc=0;
        for(int j=0;;j++)
        {
            if(s1[j]!=-1)
            {
                if(s1[j]==0) {s2[cc++]=1;s2[cc++]=0;}
                else {s2[cc++]=0;s2[cc++]=1;}
            }
            else break;
        }
        /*for(int j=0;j

最後に実装されたコード:

import java.util.*;
import java.math.*;
public class Main{
public static BigInteger[] p=new BigInteger[1010];
public static BigInteger[] s=new BigInteger[1010];
public static void init()
{
	BigInteger a=BigInteger.valueOf(0);
	BigInteger b=BigInteger.valueOf(1);
	p[1]=a;p[2]=b;s[2]=b;
	for(int i=3;i<=1000;i++)
	{
		if(i%2==0)
	    {
			p[i]=s[i-1];
			p[i]=p[i].add(b);
	    }
		else
		p[i]=s[i-1];
		s[i]=s[i-1];
		//BigInteger ss=p[i];
		s[i]=s[i].add(p[i]);
	}
}
 public static void main(String[] args) {
	 init();
 Scanner cin  = new Scanner(System.in);
  while(cin.hasNext())
  {
	  int n=cin.nextInt();
	  System.out.println(p[n]);
  }
  }
}