Tamflexの貯蔵庫

やる気のない備忘録

aoj 0041

数式 | Aizu Online Judge
いわゆる「10ゲーム」の除算がないもの. もっと簡潔に書けるかもしれないけど, どうも煩雑になってしまう.
あとnext_permutaionを使う前はsortするのを忘れてはいけない.

map<string, int> generate(vector<int> v)
{
  map<string, int> T;
  if(v.size() == 1)
  {
    if(v[0] < 0) T["("+to_string(v[0])+")"] = v[0];
    else T[to_string(v[0])] = v[0];
    return T;
  }
  else
  {
    REP(i,v.size()-1)
    {
      vector<int> a,b;
      map<string, int> s,t;
      FOR(j,0,i) a.push_back(v[j]);
      FOR(j,i+1,v.size()-1) b.push_back(v[j]);
      s = generate(a);
      t = generate(b);
      for(auto m : s) for(auto n : t)
      {
        T["("+m.first+"*"+n.first+")"] = m.second * n.second;
        T["("+m.first+"+"+n.first+")"] = m.second + n.second;
        T["("+m.first+"-"+n.first+")"] = m.second - n.second;
      }
    }
    return T;
  }
}

void solve(vector<int> v)
{
  do
  {
    map<string, int> T = generate(v);
    for(auto a : T) if(a.second == 10)
    {
      printf("%s\n",a.first.c_str());
      return;
    }
  } while(next_permutation(v.begin(),v.end()));
  printf("0\n");
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<int> a(4);
  while(1)
  {
    REP(i,4) cin >> a[i];
    if(!accumulate(a.begin(),a.end(),0)) break;
    sort(a.begin(),a.end()); solve(a);
  }
  return 0;
}