PKU 3983 快算24
http://poj.org/problem?id=3983
四つの数字を順番を変えずに、+,-,*,/,()を使って24になるような数式を出力しろというような問題。
再帰的に計算しました。
ll in[4]; string out; PI normal(PI a){ if(a.F==0)return mp(0,1); if(a.S<0)a.F*=-1,a.S*=-1; int g=__gcd(abs(a.F),abs(a.S)); return mp(a.F/g,a.S/g); } PI operator+(PI a,PI b){ int p=a.S*b.S; int c=a.F*b.S+a.S*b.F; return normal(mp(c,p)); } PI operator-(PI a,PI b){ int p=a.S*b.S; int c=a.F*b.S-a.S*b.F; return normal(mp(c,p)); } PI operator*(PI a,PI b){ int p=a.S*b.S; int c=a.F*b.F; return normal(mp(c,p)); } PI operator/(PI a,PI b){ int p=a.S*b.F; int c=a.F*b.S; return normal(mp(c,p)); } set<PI> getva(int s,int e){ set<PI> ret; if(s+1==e){ ret.insert(mp(in[s],1)); return ret; } for(int ne=s+1;ne<e;++ne){ set<PI> a=getva(s,ne); set<PI> b=getva(ne,e); FOR(it1,a)FOR(it2,b){ ret.insert(*it1+*it2); ret.insert(*it1-*it2); ret.insert(*it1*(*it2)); if(it2->F)ret.insert(*it1/(*it2)); } } return ret; } void get(int s,int e,PI va){ if(s+1==e){ out+=in[s]+'0'; return; } out+='('; for(int ne=s+1;ne<e;++ne){ set<PI> a=getva(s,ne); set<PI> b=getva(ne,e); FOR(it1,a)FOR(it2,b){ if(*it1+*it2==va){ get(s,ne,*it1); out+='+'; get(ne,e,*it2); out+=')'; return; } if(*it1-*it2==va){ get(s,ne,*it1); out+='-'; get(ne,e,*it2); out+=')'; return; } if(*it1**it2==va){ get(s,ne,*it1); out+='*'; get(ne,e,*it2); out+=')'; return; } if(it2->F && *it1/(*it2)==va){ get(s,ne,*it1); out+='/'; get(ne,e,*it2); out+=')'; return; } } } } main(){ rep(i,4)cin>>in[i]; get(0,4,mp(24,1)); cout<<out.substr(1,SZ(out)-2)<<endl; }