PKU 3445 Elementary Additions

http://poj.org/problem?id=3445
0以上の整数を以下のような集合で表す。

・0は空集合{}
・n>0はnより小さい集合を全て含む集合

1:{{}}
2:{{},{{}}}
3:{{},{{}},{{},{{}}}}
・・・

このとき、集合の形式で2つの整数が入力されるので、その和を集合の形式で出力しろというような問題。

丁度今集合と位相に苦しめられているので、自分の中ではタイムリーに感じた問題。
15を出力したら8万文字を超えたので、かなり時間がかかったっぽいです。

ただ、こういう感じの問題は面白くて好きです。

map<int,int> set2int;
int int2set[16];

void init(){
  int2set[0]=2;
  set2int[2]=0;
  for(int i=1;i<16;++i){
    int2set[i]=2+i-1;
    for(int j=0;j<i;++j)
      int2set[i]+=int2set[j];
    set2int[int2set[i]]=i;
  }
}

void print_set(int n){
  cout<<'{';
  for(int i=0;i<n;++i){
    if(i)cout<<',';
    print_set(i);
  }
  cout<<'}';
}

void solve(){
  string a,b;
  cin>>a>>b;
  print_set(set2int[SZ(a)]+set2int[SZ(b)]);
  cout<<endl;
}

main(){
  init();
  int t;
  cin>>t;
  while(t--)solve();
}