TopCoder SRM 398 Div1 Easy CountExpressions
問題
二つの数x,yが与えられる。
x,yをちょうど二度ずつ含み、"+","-","*"の演算子の演算子のみを含んでいて、
値がvalであるような式はいくつあるか求めよ。
ただし、-を単項演算子のマイナスとして使うことはできない。
演算子に優先順位はなく、先頭から順に計算する。
式は、文字列として表したときに異なるときに異なるものと数えるものとする。
制約条件
x,y≦100
valの絶対値≦100000000
方針
全列挙する。
ソースコード
string get(int tmp[2],int ord[4],int op1,int op2,int op3){ stringstream ss; const char *op="+-*"; ss<<tmp[ord[0]]; ss<<op[op1]<<tmp[ord[1]]; ss<<op[op2]<<tmp[ord[2]]; ss<<op[op3]<<tmp[ord[3]]; return ss.str(); } int op(int a,int b,int op){ if(op==0)return a+b; return op==1?a-b:a*b; } class CountExpressions { public: int calcExpressions(int x, int y, int val) { int ord[4]={},tmp[2]={x,y}; ord[2]=ord[3]=1; set<string> ans; do{ rep(op1,3)rep(op2,3)rep(op3,3){ string str=get(tmp,ord,op1,op2,op3); int v=tmp[ord[0]]; v=op(v,tmp[ord[1]],op1); v=op(v,tmp[ord[2]],op2); v=op(v,tmp[ord[3]],op3); if(v==val)ans.insert(str); } }while(next_permutation(ord,ord+4)); return ans.size(); } };