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??

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

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

  
  

   
   2
3
  
  

  
  

   
   1
1
  
  

Southeastern Europe 2005

JGShining???|???We have carefully selected several similar problems for you:?? 1006? 1030? 1032? 1007? 1143?

首先解释一下题目：

题目的大概意思很简单，就是说电脑里面存了一个初始的数字1，后面的所有规律和操作都从1开始，然后每一次产生一个变换，变换的法则如下

即 在这个数列中所有的1变换成01，所有的0变换成10，这样说可能还不明确，从1 开始，下一次则得到01（1->01），再下次则得到1001（上一次的0->10,1->01）然后得到01101001，然后依次类推.......问你经过n次变换有多少组00！（consequitive意为连续，相同的意思！）

参考网友：星夜&永恒的推理：

00只能由01推到,即01->1001->00
01只能由1,00推到,即1->01,00->1010->01.
现设a[n]表示n秒时1的个数，
b[n]表示n秒时00的个数，
c[n]表示n秒时01的个数，
由题知0,1过一秒都会产生一个1，?
所以a[n+1]=2^n.....0秒1个数，1秒2*1个数，2秒2*1*2个数，...n秒2*1*2*2*2..*2个数=2^n.
b[n+1]=c[n];
c[n+1]=a[n]+b[n],
所以b[n]=c[n-1]=a[n-2]+b[n-2]=2^(n-3)+b[n-2].
其实本题多写几个样例就能发现另一个规律b[n]=2*b[n-2]+b[n-1].?
注意本题大数相加.

/*
 * 依据递推式：b[n]=2*b[n-2]+b[n-1]
 */

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main
{

	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		BigInteger a[] = new BigInteger[1001];
		BigInteger b[] = new BigInteger[1001];
		a[0] = BigInteger.ONE;
		b[2] = BigInteger.ONE;
		b[0] = BigInteger.ZERO;
		b[1] = BigInteger.ZERO;
		for (int i = 1; i < 1001; i++)
		{
			a[i] = a[i - 1].multiply(BigInteger.valueOf(2));   //这里算a[i]的但是这里的a[i]=2^(i-2)
			if (i >= 3)					  //所以下面算b[i]时候要i要多减去一个1
			{
				b[i] = a[i - 3].add(b[i - 2]);             
			}
		}
		while (input.hasNext())
		{
			int n = input.nextInt();
			System.out.println(b[n]);
		}
	}

}