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