PKU 1348 Computing
http://poj.org/problem?id=1348
数字n1,n2,n3,n4,n5が与えられる。
この時、n1からn4と+-*/と()を自由に使ってn5を作ることが出来るかを答えろというような問題。
※n1からn4の順番は変えて良い。
順番が変更できないとしてやったらWAもらいました。
こういうあいまいなのはひどいと思います。
int in[5]; set<PI> memo[5][5]; bool vis[5][5]; PI normal( PI in){ if(in.F==0)return mp(0,1); if(in.S<0)in.F*=-1,in.S*=-1; int g=__gcd(in.F,in.S); return mp(in.F/g,in.S/g); } PI operator+(const PI& l,const PI&r){ return normal(mp(l.F*r.S+r.F*l.S,l.S*r.S)); } PI operator-(const PI&l,const PI&r){ return normal(mp(l.F*r.S-r.F*l.S,l.S*r.S)); } PI operator*(const PI&l,const PI&r){ return normal(mp(l.F*r.F,l.S*r.S)); } PI operator/(const PI&l,const PI&r){ return l*mp(r.S,r.F); } set<PI> dfs(int s,int e){ if(vis[s][e])return memo[s][e]; vis[s][e]=true; set<PI> &ret(memo[s][e]); ret.clear(); if(s+1==e){ ret.insert(mp(in[s],1)); return ret; } for(int i=s+1;i<e;++i){ set<PI> le(dfs(s,i)); set<PI> ri(dfs(i,e)); FOR(it1,le)FOR(it2,ri){ ret.insert(*it1+*it2); ret.insert(*it1-*it2); ret.insert(*it1 * (*it2)); if(it2->F)ret.insert(*it1/ *it2); } } return ret; } main(){ while(cin>>in[0],~in[0]){ memset(vis,0,sizeof(vis)); rep(i,4)cin>>in[i+1]; rep(i,5)cout<<in[i]<<' '; bool ok=false; sort(in,in+4); do{ memset(vis,0,sizeof(vis)); if(dfs(0,4).count(mp(in[4],1))){ ok=true; break; } }while(next_permutation(in,in+4)); if(ok)cout<<"OK!"<<endl; else cout<<"NO!"<<endl; } }