Expression 0041

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041

AC Code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3999801#1

関連(他の人の解法)

解法

  • 構文解析+全探索
  • ei1333さんが書いている通り、括弧のパターンは以下の通り
((a.b).(c.d))
(((a.b).c).d)
((a.(b.c)).d)
  • a,b,c,dと演算子を全探索で埋めたものを文字列として、構文解析で計算して値=10ならそれを出力
  • 他の人の解法のように、構文解析は必須ではない
  • 構文解析でもできそう?と思ったので試してみた。AC
string ops = "+-*";

void insert(string& s, VC& nums, VC& operators){
  // num
  s[2]=nums[0];
  s[6]=nums[1];
  s[11]=nums[2];
  s[16]=nums[3];
  // ops
  s[4]=operators[0];
  s[9]=operators[1];
  s[14]=operators[2];

  // 空白除去
  stringstream ss;
  for(char c : s){
    if(c!=' ') ss<<c;
  }
  s = ss.str();
}

VS f(VI V){
  VC C;
  for(ll v : V){
    char c = '0' + v;
    C.push_back(c);
  }

  VS ret;
  // 演算子全探索
  rep(i, 3){
    rep(j, 3){
      rep(k, 3){
        vector<char> operators = {ops[i], ops[j], ops[k]};

        string s;
        s = "( x . x) .(x  . x)";
        insert(s, C, operators); ret.push_back(s);

        s = "((x . x) . x) . x ";
        insert(s, C, operators); ret.push_back(s);
        
        s = "( x .(x  . x)). x";
        insert(s, C, operators); ret.push_back(s);
      }
    }
  }
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll a,b,c,d;

    MyParser par;

    while(cin>>a>>b>>c>>d){
      if(a==0) return 0;
      VI V = {a,b,c,d};
      SORT(V);
      do{
        VS lst = f(V);
        for(string s : lst){
          ll v = par.parse(s);
          debug(s, v);
          if(v==10){
            p(s);
            goto HERE;
          }
        }
      }while(next_permutation(ALL(V)));
      p(0);
HERE:
      ll a = 123;
    }   
    return 0;
}