Problem:

 

失われし数

時は3xxx年、高度に発達した文明は停滞期を迎えていた。歴史家たちはこの状況を打開しようと過去の叡智を学ぶことにした。注目したのはコンピュータ創世期の天才が残した資料である。この資料には計算式が書かれておりその計算結果が知りたいのだが、残念ながらその一部の文字が薄れて読めなくなっている。仕方がないので計算結果としてありえる最も大きい数を求めることにした。

計算式は2進数で書かれており、演算は足し算・引き算・掛け算の3種類である。括弧も用いられているが括弧内が数字のみであることはない。正確には以下のBNFで定義された文法を満たしている必要がある。

<expression> ::= <number> | <expression> <operation> <expression>
| ( <expression> <operation> <expression> )
<number> ::= <digit> | <number> <digit>
<operation> ::= + | - | *
<digit> ::= 0 | 1

当時のコンピュータの計算能力の限界により、数字は0以上210未満の整数であり計算中もこの範囲を出ることはない。ただし計算は括弧内を先に行い、掛け算は足し算・引き算より先に行う。それ以外の場合は左から順に計算する。

Input

入力は1行からなり、解読すべき数式が1つ与えられる。数式は1文字以上100文字以下である。1つの数式について最大5文字が読めなくなっていて、「.」で表現されている。与えられる数式に含まれる文字は01+-*().のいずれかである。

Constraints

数式は1文字以上100文字以下

改行を除くすべての文字は01+-*().のいずれか

.の個数は5個以下

Output

元の数式として考えられるものの内、計算結果が最大となるものを求め、計算結果を10進法で出力せよ。読めなくなっている文字をどのように埋めても元の数式と考えられるものを作れないときは-1を出力せよ。

Sample Input 1

000

Output for the Sample Input 1

0

Sample Input 2

0.0

Output for the Sample Input 2

2

Sample Input 3

...

Output for the Sample Input 3

7

Sample Input 4

(1.1)

Output for the Sample Input 4

2

Sample Input 5

0-1.

Output for the Sample Input 5

-1



Sample input:
000


Sample output:
0

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    e = LI()
    d = defaultdict(int)
    for i in e:
        d[i] += 1
    for i in d.values():
        if i != 2:
            print("no")
            break
    else:
        print("yes")
    return

#B
def B():
    n = I()
    a = LI()
    a.sort()
    ans = -float("inf")
    for c in range(n):
        for d in range(c):
            m = a[c]-a[d]
            for i in range(n)[::-1]:
                if i != c and i != d:
                    e = i
                    break
            for i in range(e)[::-1]:
                if i != c and i != d:
                    b = i
                    break
            ans = max(ans, (a[e]+a[b])/m)
    print(ans)
    return

#C
def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)

    s = input()
    n = len(s)
    if s.count("(") == 0:
        s = float(s)
        b = 10**(n-2)
        a = round(s*b)
        g = gcd(a,b)
        a //= g
        b //= g
    else:
        n = s.find("(")
        t = float(s[:n])
        b = 10**(n-2)
        a = round(t*b)
        g = gcd(a,b)
        a //= g
        b //= g
        l = (s.find("(")-s.find(".")-1)
        s = s[n+1:-1]
        m = len(s)
        c = round(float(s))
        d = (10**m-1)*10**l
        g = gcd(c,d)
        c //= g
        d //= g
        a = a*d+b*c
        b = b*d
        g = gcd(a,b)
        a //= g
        b //= g
    print(str(a)+"/"+str(b))
    return

#D
def D():
    return

#E
def E():
    def dfs(d,k,s):
        if d == n:
            ans.append(k)
        else:
            b = [block[d][i] for i in range(8)]
            if sum(b[:4]) == 0:
                b = b[4:]+[0,0,0,0]
            dfs(d+1,*check(b,k,s))
            if not (b[0]|b[1]|b[4]|b[5]):
                b_ = [b[2],b[3],0,0,b[6],b[7],0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[1]|b[3]|b[5]|b[7]):
                b_ = [0,b[0],0,b[2],0,b[4],0,b[6]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[2]|b[3]|b[6]|b[7]):
                b_ = [0,0,b[0],b[1],0,0,b[4],b[5]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[2]|b[4]|b[6]):
                b_ = [b[1],0,b[3],0,b[5],0,b[7],0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[1]|b[2]|b[3]|b[5]|b[6]|b[7]):
                b_ = [0,0,0,b[0],0,0,0,b[4]]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[2]|b[3]|b[4]|b[6]|b[7]):
                b_ = [0,0,b[1],0,0,0,b[5],0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[1]|b[3]|b[4]|b[5]|b[7]):
                b_ = [0,b[2],0,b[6],0,0,0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
            if not (b[0]|b[1]|b[2]|b[4]|b[5]|b[6]):
                b_ = [b[3],0,0,0,b[7],0,0,0]
                if sum(b_):
                    dfs(d+1,*check(b_,k,s))
    def check(b,k,s):
        i = 19
        k_ = k
        s_ = [[s[i][j] for j in range(4)] for i in range(20)]
        while i >= 1 and not ((b[0]&s[i-1][0])|(b[1]&s[i-1][1])|(b[2]&s[i-1][2])|(b[3]&s[i-1][3])|(b[4]&s[i][0])|(b[5]&s[i][1])|(b[6]&s[i][2])|(b[7]&s[i][3])):
            i -= 1
        s_[i] = [s_[i][j]+b[j] for j in range(4)]
        s_[i+1] = [s_[i+1][j]+b[j+4] for j in range(4)]
        i = 0
        while i < 20:
            if sum(s_[i]) == 4:
                k_ += 1
                for j in range(i,19):
                    s_[j] = [s_[j+1][l] for l in range(4)]
                s_[19] = [0,0,0,0]
                i -= 1
            i += 1
        return k_,s_

    while 1:
        h,n = LI()
        if h == n == 0:
            break
        s = [[0,0,0,0] for i in range(20)]
        for i in range(h):
            c = S()
            c += S()
            s[i] = [1 if c[j] == "#" else 0 for j in range(4)]
        block = [[0,0,0,0,0,0,0,0] for i in range(n)]
        for i in range(n):
            b = S()
            b += S()
            b += S()
            b += S()
            block[i] = [1 if b[j] == "#" else 0 for j in range(8)]
        ans = []
        dfs(0,0,s)
        print(max(ans))
    return

#F
def F():
    def dfs(d,k):
        if d == len(s):
            t.append(k)
        else:
            if s[d] == ".":
                for i in range(2):
                    dfs(d+1,k+[str(i)])
                for i in "+-*()":
                    dfs(d+1,k+[i])
            else:
                dfs(d+1,k+[s[d]])

    def parse_expr(s,i):
        if i == float("inf"):
            return -1,float("inf")
        f = s[i-1] == "("
        k = 0
        t,i,k = parse_term(s,i,k)
        while i < len(s) and s[i] in "+-":
            k += 1
            op,i = parse_op(s,i)
            t_,i,k = parse_term(s,i,k)
            t = calc(op,t,t_)
            if t >= 1024 or t < 0:
                return -1,float("inf")
        if f and not k:
            return -1,float("inf")
        return t,i

    def parse_term(s,i,k):
        f,i = parse_factor(s,i)
        while i < len(s) and s[i] == "*":
            k += 1
            op,i = parse_op(s,i)
            f_,i = parse_factor(s,i)
            f = calc(op,f,f_)
            if f >= 1024 or f < 0:
                return -1,float("inf"),k
        return f,i,k

    def parse_op(s,i):
        return s[i],i+1

    def parse_factor(s,i):
        if i >= len(s):
            return -1,float("inf")
        if s[i] == "(":
            i += 1
            e,i = parse_expr(s,i)
            if i >= len(s) or s[i] != ")":
                return -1,float("inf")
            i += 1
            return e,i
        else:
            if not s[i].isdecimal():
                return -1,float("inf")
            n = int(s[i])
            i += 1
            while i < len(s) and s[i].isdecimal():
                n *= 2
                n += int(s[i])
                i += 1
            if n >= 1024 or n < 0:
                return -1,float("inf")
            return n,i

    def calc(op,a,b):
        if op == "+":
            return a+b
        elif op == "-":
            return a-b
        elif op == "*":
            return a*b


    s = S()
    f = defaultdict(lambda : 0)
    for i in range(2):
        f[str(i)] += 1
    t = []
    dfs(0,[])
    ans = -1
    for s in t:
        e,i = parse_expr(s,0)
        if i == len(s):
            ans = max(ans,e)
    print(ans)
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(s):
        ca = '01+-*()'
        sa = s.split('.')
        r = -1
        sl = len(sa)

        fm = {}
        def _f(s):
            if s in fm:
                return fm[s]
            if ')' in s:
                ri = s.index(')')
                if len(s) > ri+1 and s[ri+1] in '01':
                    fm[s] = -1
                    return -1
                li = -1
                for i in range(ri-1,-1,-1):
                    if s[i] == '(':
                        li = i
                        break
                if li < 0 or li > 0 and s[li-1] in '01':
                    fm[s] = -1
                    return -1
                ts = s[li+1:ri]
                if '+' not in ts and '-' not in ts and '*' not in ts:
                    fm[s] = -1
                    return -1
                tr = _f(ts)
                if tr == -1:
                    fm[s] = -1
                    return -1
                fm[s] = _f(s[:li] + tr + s[ri+1:])
                return fm[s]
            if '(' in s:
                fm[s] = -1
                return -1

            l = len(s)
            if '*' in s:
                oi = s.index('*')
                li = oi
                for i in range(oi-1,-1,-1):
                    if s[i] not in '01':
                        break
                    li = i
                ri = oi
                for i in range(oi+1,l):
                    if s[i] not in '01':
                        break
                    ri = i
                if li == oi or ri == oi:
                    fm[s] = -1
                    return -1
                t = int(s[li:oi], 2)
                u = int(s[oi+1:ri+1], 2)
                tu = t * u
                if t < 0 or t >= 1024 or u < 0 or u >= 1024 or tu < 0 or tu >= 1024:
                    fm[s] = -1
                    return -1
                ts = bin(tu)[2:]
                fm[s] = _f(s[:li] + ts + s[ri+1:])
                return fm[s]
            pi = inf
            mi = inf
            if '+' in s:
                pi = s.index('+')
            if '-' in s:
                mi = s.index('-')
            if pi == inf and mi == inf:
                t = int(s, 2)
                fm[s] = s
                if t < 0 or t >= 1024:
                    fm[s] = -1
                return fm[s]
            oi = min(pi, mi)
            li = oi
            for i in range(oi-1,-1,-1):
                if s[i] not in '01':
                    break
                li = i
            ri = oi
            for i in range(oi+1,l):
                if s[i] not in '01':
                    break
                ri = i
            if li == oi or ri == oi:
                fm[s] = -1
                return -1
            t = int(s[li:oi], 2)
            t = int(s[li:oi], 2)
            u = int(s[oi+1:ri+1], 2)
            tu = t + u
            if oi == mi:
                tu = t - u
            if t < 0 or t >= 1024 or u < 0 or u >= 1024 or tu < 0 or tu >= 1024:
                fm[s] = -1
                return -1
            ts = bin(tu)[2:]
            fm[s] = _f(s[:li] + ts + s[ri+1:])
            return fm[s]


        for ci in itertools.product(ca, repeat=sl-1):
            t = ''
            for i in range(len(ci)):
                t += sa[i]
                t += ci[i]
            t += sa[-1]
            tr = _f(t)
            if tr != -1:
                tr = int(tr, 2)
                if tr >= 1024 or tr < 0:
                    tr = -1
            if r < tr:
                r = tr
        # for k in sorted(fm.keys()):
        #     if fm[k] == -1:
        #         continue
        #     print(k, fm[k])
        return r

    while 1:
        n = S()
        if n == 0:
            break
        rr.append(f(n))
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
from itertools import product
import time
def ok(s):
    if '(+' in s or '(-' in s or '(*' in s or '++' in s or '+-' in s or '-+' in s \
    or '--' in s or '**' in s or '*+' in s or '*-' in s:
        return False
    if '(' in s or ')' in s:
        dic={}
        count=-1
        for c in s:
            if c=='(':
                count+=1
                dic[count]=0
            elif c==')':
                if dic[count]==0:
                    return False
                count-=1
            elif c in '+-*' and count in dic:
                dic[count]+=1
        return True
    else:
        return True

def check(s):
    i=0
    ans=''
    tmp=[]
    try:
        while i<len(s):
            if s[i] in '01':
                tmp.append(s[i])
            else:
                if len(tmp):
                    t=''.join(tmp)
                    t=str(int(t,2))
                    if int(t)>=1024:
                        return -99999999
                    ans+=t
                ans+=s[i]
                tmp=[]
            i+=1
        if len(tmp):
            t=''.join(tmp)
            t=str(int(t,2))
            ans+=t
    except:
        return -99999999
    try:
        if ok(ans):
            xxx=eval(ans)
            if '-' not in ans and xxx<1024:
                return xxx
            elif '-' in ans and xxx<1024:
                for i in range(len(ans)):
                    if ans[i]=='-':
                        mid=i
                        r,l=mid-1,mid+1
                        count=0
                        while r>=0:
                            if ans[r]==')':
                                count+=1
                            elif ans[r]=='(':
                                count-=1
                                if count<0:
                                    r+=1
                                    break
                            if count==0 and ans[r] in '+-':
                                r+=1
                                break
                            r-=1
                        r=max(r,0)
                        count=0
                        while l<len(ans):
                            if ans[l]=='(':
                                count+=1
                            elif ans[l]==')':
                                count-=1
                                if count<0:
                                    break
                            if count==0 and ans[l] in '+-':
                                break
                            l+=1
                        a,b=eval(ans[r:mid]),eval(ans[mid+1:l])
                        if a>=1024 or b>=1024 or \
                        a - b <0:
                            return -99999999
                return xxx
            else:
                return -99999999
        else:
            return -99999999
    except:
        return -99999999

s=input().split('.')
mx=-1
hoge = product('01+-*()', repeat=len(s)-1)
for table in hoge:
    tmp=s[0]
    i=1
    for c in table:
        tmp+=c+s[i]
        i+=1
    mx=max(mx,check(tmp))
print(mx)