POJ 2876 - Cantoring Along

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

概要

オーダーが \(N\) のカントール集合を答える．

オーダーが \(N\) のカントール集合は以下の手順によって作られる．

  1. \(3 ^ N\) 個の - を並べて1つの線を作る
  2. 各線について，3等分した中央の線を空白に置き換えて線を2つに分ける
  3. 各線が1つの - になるまで 2 を繰り返す

制約

解法

オーダー \(N\) のカントール集合はオーダー \(N+1\) のカントール集合の部分構造になっていることを利用して，予めオーダー12までの全集合を生成しておいて答える．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   string dp[13];
 7   dp[0] = "-";
 8   for (int i = 1; i <= 12; i++) {
 9     dp[i] = dp[i-1] + string(dp[i-1].size(), ' ') + dp[i-1];
10   }
11   int N;
12   while (cin >> N) {
13     cout << dp[N] << endl;
14   }
15   return 0;
16 }
poj/2876.cc