Algoogle

Algorithm for Programming Contest

AOJ 0041 Expression

Category: AOJ Tag: brute-force

Expression

問題概要


解法


使う演算子を3つ決めて4つの数字と一緒に並び替えて計算する.
並び替える際, 計算不能なものは除外すること.
結果が10なら中置記法にしたものを答えとして出す.

コード


(0041.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

const string op = "+-*";
int n[4];
bool used[8];
string ans;
string seq;

pair<int,string> calc(string rpol){
    stack<int> st;
    stack<string> exp;
    rep(i,rpol.size()) {
        int t = op.find(rpol[i]);
        if(t < 0){
            st.push(rpol[i]-'0');
            string tmp = "";
            tmp += rpol[i];
            exp.push(tmp);
        }
        else {
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();
            string r = exp.top(); exp.pop();
            string s = exp.top(); exp.pop();
            exp.push("("+r+rpol[i]+s+")");
            switch (t){
            case 0: a += b; break;
            case 1: a -= b; break;
            case 2: a *= b; break;
            }
            st.push(a);
        }
    }
    return mp(st.top(), exp.top());
}

bool dfs(string rpol, int cnt){
    if(rpol.size() == 7){
        pair<int, string> res = calc(rpol);
        if(res.fst == 10){
            ans = res.snd;
            return true;
        }
        else return false;
    }

    rep(i,7)if(!used[i]){
        if(i > 3 && cnt < 2) continue;
        used[i] = true;
        if(dfs(rpol+seq[i],i>3? cnt-1: cnt+1)) return true;
        used[i] = false;
    }
    return false;
}

int main(){
    while(scanf("%d%d%d%d",n,n+1,n+2,n+3),n[0]){
        seq = "";
        ans = "0";
        memset(used,0,sizeof(used));
        rep(i,4) seq.pb(char(n[i]+'0'));
        rep(i,3){
            repi(j,i,3){
                repi(k,j,3){
                    seq.pb(op[i]); seq.pb(op[j]); seq.pb(op[k]);
                    if(dfs("", 0)) break;
                    seq.erase(seq.begin()+4,seq.end());
                }
                if(ans != "0") break;
            }
            if(ans != "0") break;
        }
        cout << ans << endl;
    }
    return 0;
}

Comments