Algoogle

Algorithm for Programming Contest

AOJ 2428 Lost Number

Category: AOJ Tag: parsing

Lost Number

問題概要


最大5箇所穴が空いた数式が与えられるので, 考えうる最大の計算結果を求めよ.
ただし計算途中や結果の数は0以上1024未満である.
計算出来るパターンがない場合は−1を出力しろ.

解法


穴埋めの場所は高々5個で候補が7個なので全て試す.
面倒なのは計算で, 掛け算の優先順位が高い.
そこですべての演算子の対応する2項を括弧でくくってしまって優先順位を考えないようにする.
無効な式や数値が出てきたら−1を返すようにする.
無効な式を見つけたら例外を投げると簡単に書けて良い.

コード


(2428.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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
const string cs = "01+-*()";
const string ops = "+-*";
string s, eq;
int K, pos;
int use[8];

inline bool valid(int &a){ return a >= 0 and a <= 1023;}
bool valid(char c, char d){
    if(count(all(ops),c) and count(all(ops),d)) return 0;
    if(c == '(' and d == ')' or c == ')' and d == '(') return 0;
    if(c == '(' and count(all(ops), d)) return 0;
    if(d == '(' and isdigit(c)) return 0;
    if(c == ')' and isdigit(d)) return 0;
    if(d == ')' and count(all(ops), c)) return 0;
    return 1;
}
bool valid(){
    int d = 0;
    if(count(all(ops),eq[0]) or eq[0] == ')' or
       count(all(ops),eq[eq.size()-1]) or eq[eq.size()-1] == '(')
        return 0;
    rep(i,eq.size()){
        if(eq[i] == '(') d++;
        else if(eq[i] == ')') d--;
        if(d < 0) return 0;
        if(i and !valid(eq[i-1], eq[i])) return 0;
    }
    if(d) return 0;
    return 1;
}

int pack(int m){
    int d = 0, l = m-1, r = m+1, ret = 0;
    if(isdigit(eq[l]))
        while(l >= 0 and isdigit(eq[l])) l--;
    else{
        l--; d--;
        while(d){
            if(eq[l] == ')') d--;
            else if(eq[l] == '(') d++;
            l--;
        }
    }
    if(isdigit(eq[r]))
        while(r < eq.size() and isdigit(eq[r])) r++;
    else{
        r++; d++;
        while(d){
            if(eq[r] == ')') d--;
            else if(eq[r] == '(') d++;
            r++;
        }
    }
    if(l < 0 or eq[l] != '(' or r >= eq.size() or eq[r] != ')'){
        eq.insert(l+1,"(");
        eq.insert(r+1,")");
        return 1;
    }
    return 0;
}

void normalize(){
    rep(i,eq.size())
        if(eq[i] == '*')
            i += pack(i);
    rep(i,eq.size())
        if(eq[i] == '+' or eq[i] == '-')
            i += pack(i);
}

int number(){
    int ret = 0;
    while(pos < eq.size() and isdigit(eq[pos])){
        ret = (ret << 1) + eq[pos++]-'0';
        if(ret > 1023) throw -1;
    }
    if(!valid(ret)) throw -1;
    return ret;
}

int expr(){
    if(eq[pos] != '(') return number();
    pos++;
    int a = expr();
    if(!valid(a)) throw -1;
    char op = eq[pos++];
    if(ops.find(op) == string::npos) throw -1;
    int b = expr();
    pos++;
    if(!valid(b)) throw -1;
    int ret = 0;
    if(op == '*') ret = a*b;
    else if(op == '+') ret = a+b;
    else if(op == '-') ret = a-b;
    if(!valid(ret)) throw -1;
    return ret;
}

int calc(){
    eq = s;
    int idx = 0;
    rep(i,s.size()) if(eq[i] == '.')
        eq[i] = cs[use[idx++]];
    pos = 0;
    if(!valid()) throw -1;
    normalize();
    int ret = expr();
    //    cerr << eq << " = " << ret << endl;
    if(!valid(ret)) throw -1;
    return ret;
}

int rec(int cur){
    int ret = -1;
    if(cur == K){
        try{
            ret = calc();
        } catch(int e){
            ret = e;
        }
        return ret;
    }
    rep(i,7){
        use[cur] = i;
        ret = max(ret, rec(cur+1));
    }
    return ret;
}

int solve(){
    K = 0;
    rep(i,s.size()) if(s[i] == '.') K++;
    return rec(0);
}


signed main(){
    cin >> s;
    cout << solve() << endl;
    return 0;
}

Comments