POJ 2680 - Computer Transformation

http://poj.org/problem?id=2680

概要

1 からスタートして，各ステップ毎に

• 1 は 01 に変換
• 0 は 10 に変換

ということを繰り返す．

例えば最初の3ステップは 1 → 01 → 1001 → 01101001 となる．

n ステップ後の状態に，連続する 0 が何個出現するか答える．

制約

• 0 < n <= 1000

解法

00 という列は

• 01 → 1001

という形でしか生じない．したがって0が3つ以上連続することもない．

一方 01 という列は

• 1 → 01
• 00 → 1010

という形でしか生じない．

i ステップ後の 00 の数を a[i] とすると，i ステップ後の 01 の数は，i ステップ後の 1 の数は 2^(i-1) なので a[i-1] + 2^(i-2) である． したがって a[i] = a[i-2] + 2^(i-3) が成り立つ．

よって

• a[1] = 0
• a[2] = 1
• a[i] = a[i-2] + 2^(i-3)

という漸化式に従って a[1000] まで求めておけばいい． 2^(i-3) という項があることからわかるように，多倍長演算が必要なので Java で通した．

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main {
 5   public static void main(String[] args) {
 6     BigInteger two = new BigInteger("2");
 7     BigInteger[] a = new BigInteger[1000];
 8     a[0] = BigInteger.ZERO;
 9     a[1] = BigInteger.ONE;
10     for (int i = 2; i < 1000; i++) {
11       a[i] = a[i-2].add(two.pow(i-2));
12     }
13 
14     Scanner cin = new Scanner(System.in);
15     while (cin.hasNext()) {
16       System.out.println(a[cin.nextInt()-1]);
17     }
18   }
19 }