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(); }