2680 Computer Transformation

問題概要

0,1からなる文字列の0を10,1を01に置き換える操作を、
最初に1から始めてn回行う。

操作後の文字列に00の出現する回数を求めよ。
n≦1000とする。

解法

小さい数(n≦10くらい）で試すと、漸化式はa[i]=a[i-1]+(-1)^(i+1)となっていることがわかる。

答えは大きくなるのでBigInteger等で計算する。
また、n≦1000までを最初に全て計算しておく。

ソースコード

class Main {
	public static void main(String[] args) {
		new Main().new PKU2680().run();
	}
	class PKU2680{
		void run(){
			BigInteger ret[]=new BigInteger[1000];
			ret[0]=BigInteger.ZERO;
			for(int i=1;i<1000;i++){
				ret[i]=ret[i-1].multiply(BigInteger.valueOf(2));
				if(i%2==0)ret[i]=ret[i].subtract(BigInteger.ONE);
				else ret[i]=ret[i].add(BigInteger.ONE);
			}
			int n;
			Scanner sc=new Scanner(System.in);
			while(sc.hasNextInt()){
				n=sc.nextInt();
				System.out.println(ret[n-1]);
			}
		}
	}
}