Problem:


Ononokomachi's Edit War

-->

小野小町の編集合戦

近所に住む秋田博士は在野の歴史研究家であり, 最近小野小町に関する新たな古文書を発見したそうだ.

小野小町が交際を望む深草少将に100夜欠かさず通い続けることを条件に出したという伝説は広く知られているが, 彼の主張によると, この発見により新たに, 2人は毎晩とあるゲームをしていたことがわかったという.

そのルールは以下の通りである.

最初に召使が編集回数と有効な数式を決める

深草少将, 小野小町, 深草少将, 小野小町,... という順に交互に数式を編集する

深草少将と小野小町が合わせて召使が決めた回数の編集を行うとゲームは終了する

1回の数式の編集において, 数式に 1 文字追加, または数式から 1 文字削除のいずれかができる

数式が無効になるような編集をしてはならない

有効な数式の詳しい定義は下記を見てほしい.

このゲームにおいて, 最終的な数式の計算結果が大きいほど,
深草少将の通うべき日数を減らしてあげることになっていたらしい.
すなわち, 深草少将は結果を最大化させることが目的であり,
小野小町は最小化させることが目的である.

ところで, 古文書には召使が決めた編集回数と数式については記録が残っていたのであるが,
肝心の結果の方は虫食いにより読めなくなってしまっていた.
博士は結果に興味を持ち, 自力で計算してみようと思ったものの, ゲーム理論が得意でない彼には難しすぎたため, とりあえず近所のあなたに助けを求めてきたようだ.
そこであなたはプログラムを書いて彼に協力することにした.

平安時代に現代的な数式があったということに胡散臭さを感じるかもしれないが, 近所付き合いという大義の前に, そのような些事を気にするべきではないのだ.

有効な数式の定義

このゲームにおける有効な数式とは, "(", ")", "*", "+", "-", "&", "^", "|", "0" - "9" の 18 種類の文字のみからなる空でない文字列であり,
さらに, 有限個の項を2項演算子で結合したものである.
書き下すと,

[項][2項演算子][項][2項演算子]...[2項演算子][項]

のようになる.

項とは, "("[有効な数式]")" のようにカッコで挟まれた有効な数式, または正の整数である.
正の整数は, 先頭に "0" を持たない, 数字のみからなる文字列である.

最後に, 2項演算子とは, "*", "+", "-", "&", "^", "|" のいずれかちょうど 1 文字である.
詳しい定義は下記を見てほしい.

以上の規則から,

"1+-1" のように2文字あるので有効な2項演算子でないもの,

"+1" のように項を2項演算子で結合したものでないもの,

"2)", "(3" のようにカッコの対応がとれていないので有効な項でないもの,

"0", "01" のように 0 で始まり有効な正の整数の表現でないもの

などは, 無効な数式であるとみなされる.

一方で,

"(1+2)" のように最も外側にカッコが付いているもの,

"&#x28;(1+2))*3" のように2重にカッコが付いているもの,

"(1)+3" のように括弧内に数しかないもの,

"(1*2)+3" のように2項演算子の優先順位と同じになるもの,

などは, 冗長ではあるが, 上の規則の下では受理され, 有効な数式とみなされることに注意してほしい.

2項演算子の種類

このゲームにおいて, 2項演算子は "*", "+", "-", "&", "^", "|" の 6 種類がある.
それぞれ, 乗算, 加算, 減算, ビットごとの論理積, ビットごとの排他的論理和, ビットごとの論理和である.
なお, ビット演算を考えるとき, 負の数は十分大きな桁数の2の補数で表現されていると見なされる. すなわち, 普通の符号付き整数型で計算すると考えてもよい.

また, 優先順位は高い方から,

*

+, -

&

^

|

の順である.

なお, + より * の方が優先順位が高いとは,

2*4+3*5

のような式において * のほうが先に計算されるという意味であり, 言い換えると,

(2*4)+(3*5)

となるということである.

また, すべての2項演算子は左結合であるとする.
これは,

2^4^3^5

のような式において左から順に計算するという意味であり, 言い換えると,

((2^4)^3)^5

となるということである.

Input

入力は複数のデータセットから構成される. 各データセットは1回のゲームで召使が決めた編集回数と数式を表し, その形式は以下の通りである.

N Expression

N は召使が決めた編集回数であり, 1 &#8804; N &#8804; 11 と仮定してよい.
また, Expression は召使が決めた数式であり, "(", ")", "*", "+", "-", "&", "^", "|", "0" - "9" の 18 種類の文字のみからなる, 7 文字以下の空でない文字列として与えられる.
なお, 上で定義した有効な数式のみが与えられ, 無効な数式が与えられることはないと仮定してよい.

入力の終わりは,

0 #

で表される.

なお, データセットは 99 個以下であると仮定してよい.

Output

各データセットに対して, 両者が最善を尽くしたときの最終的な数式の計算結果を 1 行で出力せよ.
それ以外の余計な文字を出力してはならない.

Sample Input

1 1
2 2
3 1+2*3-4
3 1|2^3&4
3 (1+2)*3
3 1-1-1-1
0 #

Output for Sample Input

91
2
273
93
279
88



Sample input:
1 1
2 2
3 1+2*3-4
3 1|2^3&4
3 (1+2)*3
3 1-1-1-1
0 #


Sample output:
91
2
273
93
279
88

Submission status: Wrong Answer

Solution code:
# undo が出来るゲームは全て2手だけ見ればよい
ops = ["+", "*", "-", "&", "^", "|"]
numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]


def check(x):
    # +*
    op = 0
    for c in x:
        if c in ops:
            op += 1
            if op >= 2:
                return False
        else:
            op = 0
    # +...
    for op in ops:
        if x.startswith(op):
            return False
        if ("(" + op) in x:
            return False
    # 0がないか
    zero_ok = False
    for c in x:
        if not zero_ok and c == "0":
            return False
        if c in ops:
            zero_ok = False
        elif c in numbers:
            zero_ok = True
        else:  # ( )
            zero_ok = False
    try:
        val = int(eval(x))
        return val
    except:
        return False


def get_nexts(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != False:
            result.append((val, y))
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != False:
                result.append((val, y))
    return result


while True:
    n, x = input().split(" ")
    n = int(n)
    if n == 0:
        quit()
    nexts = get_nexts(x)
    if n == 1:
        nexts.sort(key=lambda a: - a[0])
        print(nexts[0][0])
        continue
    maxval = eval(x)
    tele = x
    minvals = []
    for (val, y) in nexts:
        nextss = get_nexts(y)
        nextss.sort(key=lambda a: a[0])
        minvals.append(nextss[0][0])
        if maxval < nextss[0][0]:
            maxval = nextss[0][0]
            tele = nextss[0][1]
    if n % 2 == 0:
        print(max(minvals))
        continue
    nexts = get_nexts(tele)
    if n % 2 == 1:
        nexts.sort(key=lambda a: -a[0])
        print(nexts[0][0])
        continue

Submission status: Wrong Answer

Solution code:
def solve():
    N, S = input().split(' ')
    N = int(N)
    if N == 0 and S == '#': return False;
    if N % 2 == 0: 
        print(eval(S))
        return True
    insert_S = ["*", "+", "-", "&", "^", "|"] + [str(i) for i in range(10)]
    ans = int(eval(S))
    for i in range(len(S)):
        for j in insert_S:
            s = S[:i] + j + S[i:]
            try:
                tmp = int(eval(s))
                ans = max([ans, tmp])
            except:
                pass
    for i in range(len(S)):
        try:
            s = S[:i] + S[i+1:]
            tmp = int(eval(s))
            ans = max([ans, tmp])
        except:
            pass
    print(ans)
    return True

if __name__ == '__main__':
    while True:
        if solve() == False:
            break;

Submission status: Accepted

Solution code:
# undo が出来るゲームは全て2手だけ見ればよい
ops = ["+", "*", "-", "&", "^", "|"]
numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]


def check(x):
    # +*
    op = 0
    for c in x:
        if c in ops:
            op += 1
            if op >= 2:
                return None
        else:
            op = 0
    # +...
    for op in ops:
        if x.startswith(op):
            return None
        if ("(" + op) in x:
            return None
    # 0がないか
    zero_ok = False
    for c in x:
        if not zero_ok and c == "0":
            return None
        if c in ops:
            zero_ok = False
        elif c in numbers:
            zero_ok = True
        else:  # ( )
            zero_ok = False
    try:
        val = int(eval(x))
        return val
    except:
        return None


def get_nexts(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != None:
            result.append((val, y))
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != None:
                result.append((val, y))
    return result


while True:
    n, x = input().split(" ")
    n = int(n)
    if n == 0:
        quit()
    nexts = get_nexts(x)
    if n == 1:
        nexts.sort(key=lambda a: - a[0])
        print(nexts[0][0])
        continue
    maxval = eval(x)
    tele = x
    minvals = []
    for (val, y) in nexts:
        nextss = get_nexts(y)
        nextss.sort(key=lambda a: a[0])
        minvals.append(nextss[0][0])
        if maxval < nextss[0][0]:
            maxval = nextss[0][0]
            tele = nextss[0][1]
    if n % 2 == 0:
        print(max(minvals))  # 999+9999 -> 9&99+9999
        continue
    nexts = get_nexts(tele)
    if n % 2 == 1:
        nexts.sort(key=lambda a: -a[0])
        print(nexts[0][0])
        continue

Submission status: Accepted

Solution code:
# undo が出来るゲームは全て2手だけ見ればよい
ops = ["+", "*", "-", "&", "^", "|"]
numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]


def check(x):
    # +*
    op = 0
    for c in x:
        if c in ops:
            op += 1
            if op >= 2:
                return None
        else:
            op = 0
    # +...
    for op in ops:
        if x.startswith(op):
            return None
        if ("(" + op) in x:
            return None
    # 0がないか
    zero_ok = False
    for c in x:
        if not zero_ok and c == "0":
            return None
        if c in ops:
            zero_ok = False
        elif c in numbers:
            zero_ok = True
        else:  # ( )
            zero_ok = False
    try:
        val = int(eval(x))
        return val
    except:
        return None


def get_nexts(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != None:
            result.append((val, y))
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != None:
                result.append((val, y))
    return result


while True:
    n, x = input().split(" ")
    n = int(n)
    if n == 0:
        quit()
    nexts = get_nexts(x)
    if n % 2 == 1:
        nexts.sort(key=lambda a: - a[0])
        print(nexts[0][0])
        continue
    minvals = []
    for (val, y) in nexts:
        nextss = get_nexts(y)
        nextss.sort(key=lambda a: a[0])
        minvals.append(nextss[0][0])
    print(max(minvals))

Submission status: Accepted

Solution code:
# undo が出来るゲームは全て2手だけ見ればよい
ops = ["+", "*", "-", "&", "^", "|"]
numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]


def check(x):
    # +*
    op = 0
    for c in x:
        if c in ops:
            op += 1
            if op >= 2:
                return None
        else:
            op = 0
    # +...
    for op in ops:
        if x.startswith(op):
            return None
        if ("(" + op) in x:
            return None
    # 0がないか
    zero_ok = False
    for c in x:
        if not zero_ok and c == "0":
            return None
        if c in numbers:
            zero_ok = True
        else:
            zero_ok = False
    try:
        return int(eval(x))
    except:
        return None


def get_nexts(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != None:
            result.append((val, y))
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != None:
                result.append((val, y))
    return result


def get_nexts_val(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != None:
            result.append(val)
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != None:
                result.append(val)
    return result


while True:
    n, x = input().split(" ")
    n = int(n)
    if n == 0:
        quit()
    nexts = get_nexts(x)
    if n % 2 == 1:
        nexts.sort(key=lambda a: - a[0])
        print(nexts[0][0])
        continue
    minvals = []
    for (val, y) in nexts:
        nextss = get_nexts_val(y)
        nextss.sort()
        minvals.append(nextss[0])
    print(max(minvals))

Submission status: Accepted

Solution code:
from string import digits
import sys
readline = sys.stdin.readline
write = sys.stdout.write
memo = {}
def parse(S):
    key = "".join(S)
    if key in memo:
        return memo[key]
    S = S + ["$"]
    cur = 0
    ALL = 2**32-1
    neg = 2**31
    def expr2():
        nonlocal cur
        r0 = 0
        op = "+"
        while 1:
            r1 = 1
            while 1:
                if S[cur] == "(":
                    cur += 1 # "("
                    r1 *= expr1()
                    cur += 1 # ")"
                else:
                    v = 0
                    while S[cur] in digits:
                        v = 10*v + int(S[cur])
                        cur += 1 # digits
                    r1 *= v
                if S[cur] != "*":
                    break
                cur += 1 # "*"
            if op == "+":
                r0 += r1
            else:
                r0 -= r1
            if S[cur] not in "+-":
                break
            op = S[cur]
            cur += 1 # "+-"
        return r0
    def expr1():
        nonlocal cur
        r0 = 0
        while 1:
            r1 = 0
            while 1:
                r2 = ALL
                while 1:
                    r2 &= expr2()
                    if r2 & neg:
                        r2 -= neg*2
                    if S[cur] != "&":
                        break
                    cur += 1 # "&"
                r1 ^= r2
                if S[cur] != "^":
                    break
                cur += 1 # "^"
            r0 |= r1
            if S[cur] != "|":
                break
            cur += 1 # "|"
        return r0
    memo[key] = r = expr1()
    assert len(key) == cur
    return r
def solve():
    N, S = readline().strip().split()
    N = int(N)
    S = list(S)
    if N == 0:
        return False
    N = 1 if N % 2 else 2
    memo = [{} for i in range(N+1)]
    A = "123456789"
    B = "0123456789"
    C = "*+-&^|"
    def gen(i, S):
        L = len(S)
        if S[0] in B:
            for v in A:
                yield dfs(i+1, [v] + S)
        for k in range(L):
            if k+1 < L and (S[k] == "(" or S[k] in C) and S[k+1] in B:
                for v in A:
                    yield dfs(i+1, S[:k+1] + [v] + S[k+1:])
            elif S[k] in B:
                if k+1 < L and S[k+1] in B:
                    if S[k+1] == "0":
                        continue
                    for c in C:
                        yield dfs(i+1, S[:k+1] + [c] + S[k+1:])
                for v in B:
                    yield dfs(i+1, S[:k+1] + [v] + S[k+1:])
        for k in range(L):
            if S[k] in C and S[k-1] in B and S[k+1] in B:
                yield dfs(i+1, S[:k] + S[k+1:])
            elif S[k] in B:
                if k-1 >= 0 and S[k-1] in B:
                    yield dfs(i+1, S[:k] + S[k+1:])
                elif (k == 0 or S[k-1] == "(" or S[k-1] in C) and (k+1 < L and S[k+1] in B):
                    if S[k+1] == "0":
                        continue
                    yield dfs(i+1, S[:k] + S[k+1:])
    def dfs(i, S):
        key = "".join(S)
        if key in memo[i]:
            return memo[i][key]
        if i == N:
            memo[i][key] = r = parse(S)
            return r
        if i % 2 == 0:
            memo[i][key] = r = max(gen(i, S))
        else:
            memo[i][key] = r = min(gen(i, S))
        return r
    write("%d\n" % dfs(0, S))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
INF = 100000000000000

def ev1(s):
    ans = 0
    try:
        ans = eval(s)
        if ans == (): raise Exception
        if len(s)==0: raise Exception
    except:
        ans = -INF
    return ans

def ev2(s):
    ans = 0
    try:
        ans = eval(s)
        if ans == (): raise Exception
        if len(s)==0: raise Exception
    except:
        ans = INF
    return ans

def ggg(s):
    if ev1(s)==-INF:
        return -INF
    n = len(s)
    ans = INF
    D10 = [str(x) for x in range(10)]
    D9 = [str(x) for x in range(1,10)]
    OP = ['*', '+', '-', '&', '^', '|']
    for i in range(n):
        for d in D10:
            if s[i] in D10:
                t = s[0:i] + d + s[i:]
                nxt = ev2(t)
                if nxt < ans: ans = nxt
        for d in D10:
            if s[i] in D10:
                t = s[0:i+1] + d + s[i+1:]
                nxt = ev2(t)
                if nxt < ans: ans = nxt
        for c in OP:
            if i<n-1 and (s[i] in D10) and (s[i+1] in D9):
                t = s[0:i+1] + c + s[i+1:]
                nxt = ev2(t)
                if nxt < ans: ans = nxt
        if (s[i] in D10 and ((i>0 and s[i-1] in D10) or (i<n-1 and s[i+1] in D9))) or (s[i] in OP and i>0 and i<n-1 and s[i-1] in D10 and s[i+1] in D10):
            t = s[0:i] + s[i+1:]
            nxt = ev2(t)
            if nxt < ans: ans = nxt
    return ans

while True:
    s = input().split()
    N = int(s[0])
    s = s[1]
    if N==0:
        break
    n = len(s)
    ans = -INF
    D10 = [str(x) for x in range(10)]
    D9 = [str(x) for x in range(1,10)]
    OP = ['*', '+', '-', '&', '^', '|']
    fff = ev1
    if N%2==0: fff = ggg
    for i in range(n):
        for d in D10:
            if s[i] in D10:
                t = s[0:i] + d + s[i:]
                nxt = fff(t)
                if nxt > ans: ans = nxt
        for d in D10:
            if s[i] in D10:
                t = s[0:i+1] + d + s[i+1:]
                nxt = fff(t)
                if nxt > ans: ans = nxt
        for c in OP:
            if i<n-1 and (s[i] in D10) and (s[i+1] in D9):
                t = s[0:i+1] + c + s[i+1:]
                nxt = fff(t)
                if nxt > ans: ans = nxt
        if (s[i] in D10 and ((i>0 and s[i-1] in D10) or (i<n-1 and s[i+1] in D9))) or (s[i] in OP and i>0 and i<n-1 and s[i-1] in D10 and s[i+1] in D10):
            t = s[0:i] + s[i+1:]
            nxt = fff(t)
            if nxt > ans: ans = nxt
    print(ans)

Submission status: Runtime Error

Solution code:
# undo が出来るゲームは全て2手だけ見ればよい
ops = ["+", "*", "-", "&", "^", "|"]
numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]


def check(x):
    # +*
    op = 0
    for c in x:
        if c in ops:
            op += 1
            if op >= 2:
                return False
        else:
            op = 0
    # +...
    for op in ops:
        if x.startswith(op):
            return False
        if ("(" + op) in x:
            return False
    # 0がないか
    zero_ok = False
    for c in x:
        if not zero_ok and c == "0":
            return False
        if c in ops:
            zero_ok = False
        elif c in numbers:
            zero_ok = True
        else:  # ( )
            zero_ok = False
    try:
        val = eval(x)
        return val
    except:
        return False


def get_nexts(x):
    # 削除
    result = []
    for i in range(len(x)):
        y = x[:i] + x[i + 1:]
        val = check(y)
        if val != False:
            result.append((val, y))
    # 追加
    for i in range(len(x) + 1):
        add_list = numbers + ops
        for s in add_list:
            y = x[:i] + s + x[i:]
            val = check(y)
            if val != False:
                result.append((val, y))
    return result


while True:
    n, x = input().split(" ")
    n = int(n)
    if n == 0:
        quit()
    nexts = get_nexts(x)
    if n == 1:
        nexts.sort(key=lambda a: - a[0])
        print(nexts[0][0])
        continue
    maxval = eval(x)
    tele = x
    minvals = []
    for (val, y) in nexts:
        nextss = get_nexts(y)
        nextss.sort(key=lambda a: a[0])
        minvals.append(nextss[0][0])
        if maxval < nextss[0][0]:
            maxval = nextss[0][0]
            tele = nextss[0][1]
    if n % 2 == 0:
        print(max(minvals))
        continue
    nexts = get_nexts(tele)
    if n % 2 == 1:
        nexts.sort(key=lambda a: -a[0])
        print(nexts[0][0])
        continue