POJ 2876 - Cantoring Along
http://poj.org/problem?id=2876
概要
オーダーが N のカントール集合を答える.
オーダーが N のカントール集合は以下の手順によって作られる.
- 3N 個の
-
を並べて1つの線を作る - 各線について,3等分した中央の線を空白に置き換えて線を2つに分ける
- 各線が1つの
-
になるまで 2 を繰り返す
制約
- 0≤N≤12
解法
オーダー N のカントール集合はオーダー N+1 のカントール集合の部分構造になっていることを利用して,予めオーダー12までの全集合を生成しておいて答える.
poj/2876.cc1 #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 }