AOJ0041: Expression

問題概要

---

10パズル

解法

---

括弧とか括弧とかが面倒なので面倒くさいけど場合分けで書いた。
((a.b).(c.d))
(((a.b).c).d)
((a.(b.c)).d)
多分この3通りだと思う。

ソース

---

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<sstream>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++ )
int d[4];
bool flg = false;
string s = "+-*";
int calc( int a, int op, int b){
  if( op == 0) return a + b;
  if( op == 1) return a - b;
  return a * b;
}
bool solve(int a, int b, int c){
  flg++;
  if(calc( calc( calc( d[0], a, d[1]), b, d[2]), c, d[3]) == 10){
    return printf("(((%d %c %d) %c %d) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, d[1]), b, calc( d[2], c, d[3])) == 10){
    return printf("((%d %c %d) %c (%d %c %d))\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, calc( d[1], b, d[2])), c, d[3]) == 10){
    return printf("((%d %c (%d %c %d)) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  return flg = false;
}
 
bool judge(){
  rep(i,3) rep(j,3) rep(k,3) if(solve( i, j, k)) return true;
}
int main(){
  while(flg = true){
    rep(i,4) cin >> d[i];
    if(!d[0] && !d[1] && !d[2] && !d[3]) break;
    sort(d, d + 4);
    do if(judge()) break; while(next_permutation(d,d+4));
    if(!flg) puts("0");
  }
}