PKU 1029 False coin
http://poj.org/problem?id=1029
n枚のコインがあって、一つだけ他のものと重さの違うものが混ざっている。
このとき、はかりでいくつかのコインの重さを比べたときのデータがk回分渡される。
この情報をもとに偽物のコインを絞り込めというような問題。
全てのコインについて重さが違うとしても矛盾しないものを抽出して、矛盾しないものの個数を見て出力。
昔見た時は全く解法が思いつかなかった問題でしたが、今になるとすんなり全探索が思いついて、多少は成長したのかなと思ったり思わなかったり。
set<int> ri[100],le[100]; char ch[100]; int n,k; bool isfalse(int co){ bool ok=true; rep(i,k){ switch(ch[i]){ case '=': if(ri[i].count(co)!=0 || le[i].count(co)!=0)return false; break; case '<': if(ri[i].count(co)==0)ok= false; break; case '>': if(le[i].count(co)==0)ok= false; break; } } if(ok)return true; ok=true; rep(i,k){ switch(ch[i]){ case '=': if(ri[i].count(co)!=0 || le[i].count(co)!=0)return false; break; case '<': if(le[i].count(co)==0)ok=false; break; case '>': if(ri[i].count(co)==0)ok=false; break; } } return ok; } main(){ cin>>n>>k; rep(i,k){ int nu; cin>>nu; rep(j,nu){ int t; cin>>t; le[i].insert(t); } rep(j,nu){ int t; cin>>t; ri[i].insert(t); } cin>>ch[i]; } set<int>ans; rep(i,n)if(isfalse(i+1))ans.insert(i+1); if(ans.size()==1)cout<<*ans.begin()<<endl; else cout<<0<<endl; }