Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem E
Infallibly Crack Perplexing Cryptarithm

  You are asked to crack an encrypted equation over binary numbers.

  The original equation consists only of binary digits ("0" and "1"), operator symbols ("+", "-", and "*"), parentheses ("(" and ")"), and an equal sign ("="). The encryption replaces some occurrences of characters in an original arithmetic equation by letters. Occurrences of one character are replaced, if ever, by the same letter. Occurrences of two different characters are never replaced by the same letter. Note that the encryption does not always replace all the occurrences of the same character; some of its occurrences may be replaced while others may be left as they are. Some characters may be left unreplaced. Any character in the Roman alphabet, in either lowercase or uppercase, may be used as a replacement letter. Note that cases are significant, that is, "a" and "A" are different letters. Note that not only digits but also operator symbols, parentheses and even the equal sign are possibly replaced.

  The arithmetic equation is derived from the start symbol of $Q$ of the following context-free grammar.

  

  $Q ::= E=E$

  $E ::= T | E+T | E-T$

  $T ::= F | T*F $

  $F ::= N | -F | (E) $

  $N ::= 0 | 1B $

  $B ::= \epsilon | 0B | 1B$

  

Here, $\epsilon$ means empty.

  As shown in this grammar, the arithmetic equation should have one equal sign. Each side of the equation is an expression consisting of numbers, additions, subtractions, multiplications, and negations. Multiplication has precedence over both addition and subtraction, while negation precedes multiplication. Multiplication, addition and subtraction are left associative. For example, x-y+z means (x-y)+z, not x-(y+z). Numbers are in binary notation, represented by a sequence of binary digits, 0 and 1. Multi-digit numbers always start with 1. Parentheses and negations may appear redundantly in the equation, as in ((--x+y))+z.

Write a program that, for a given encrypted equation, counts the number of different possible original correct equations. Here, an equation should conform to the grammar and it is correct when the computed values of the both sides are equal.

  For Sample Input 1, C must be = because any equation has one = between two expressions. Then, because A and M should be different, although there are equations conforming to the grammar, none of them can be correct.

  For Sample Input 2, the only possible correct equation is -0=0.

For Sample Input 3 (B-A-Y-L-zero-R), there are three different correct equations, 0=-(0), 0=(-0), and -0=(0). Note that one of the two occurrences of zero is not replaced with a letter in the encrypted equation.

Input

The input consists of a single test case which is a string of Roman alphabet characters, binary digits, operator symbols, parentheses and equal signs. The input string has at most 31 characters.

Output

Print in a line the number of correct equations that can be encrypted into the input string.

Sample Input 1

ACM

Sample Output 1

0

Sample Input 2

icpc

Sample Output 2

1

Sample Input 3

BAYL0R

Sample Output 3

3

Sample Input 4

-AB+AC-A

Sample Output 4

1

Sample Input 5

abcdefghi

Sample Output 5

0

Sample Input 6

111-10=1+10*10

Sample Output 6

1

Sample Input 7

0=10-1

Sample Output 7

0



Sample input:
ACM


Sample output:
0

Submission status: Wrong Answer

Solution code:
s = ""
ans = 0
slen = 0
d = {}
u = {
    "+": False,
    "-": False,
    "*": False,
    "0": False,
    "1": False,
    "=": False,
    "(": False,
    ")": False
}

def dfs(p):
    global slen, ans, s
    if p == slen:
        tmp = ""
        cnte = 0
        for i in s:
            if i in d:
                tmp = tmp + d[i]
                if d[i] == "=":
                    cnte = cnte + 1
            else:
                tmp = tmp + i
                if i == "=":
                    cnte = cnte + 1

        if cnte != 1:
            return
        if tmp[0] == "=" or tmp[slen - 1] == "=":
            return
        if tmp[0] == "+":
            return
        for i in range(1, slen):
            if tmp[i] == tmp[i - 1] and tmp[i] == "*":
                return
            if tmp[i] == "+" and tmp[i - 1] == "-":
                return
            if tmp[i] == "+" and tmp[i - 1] == "+":
                return
            if tmp[i] == "+" and tmp[i - 1] == "*":
                return
            if tmp[i] == "+" and tmp[i - 1] == "=":
                return
            if tmp[i] == "+" and tmp[i - 1] == "(":
                return

        lst = 2
        for i in range(slen):
            if tmp[i] == "0" or tmp[i] == "1":
                if lst == 0:
                    return
                if lst == 2 and tmp[i] == "0":
                    lst = 0
                else: lst = 1
            else: lst = 2

        tt = ""
        lastnum = False
        for i in tmp:
            if i == "0" or i == "1":
                if lastnum == False:
                    tt = tt + "0b"
                lastnum = True
            else: lastnum = False
            tt = tt + i

        try:
            (le, re) = tt.split("=")
            if eval(le) == eval(re):
                ans = ans + 1
        except Exception as e:
            pass
        return

    flag = False
    for (key, value) in u.items():
        if s[p] == key:
            flag = True
            break

    if flag or s[p] in d:
        dfs(p + 1)
    else:
        for (key, value) in u.items():
            if not value:
                d[s[p]] = key
                u[key] = True
                dfs(p + 1)
                del d[s[p]]
                u[key] = False

s = input()
slen = len(s)
dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
base = "=+-*()01"
s = input()
l = len(s)
mapping = {}
counter = {}
cnt = 0
for c in s:
    if c in base:
        continue
    if c not in mapping:
        mapping[c] = cnt
        cnt += 1
    v = mapping[c]
    counter[v] = counter.get(v, 0) + 1
if cnt > 8:
    print(0)
    exit(0)

def solve(read):
    cur = failed = 0
    def next():
        nonlocal cur
        cur += 1
    def error():
        nonlocal failed
        failed = 1
    def number():
        res = 0
        if read(cur) not in "01":
            error()
        first = 1
        while 1:
            c = read(cur)
            if c not in "01":
                break
            if not first and res == 0:
                error()
            res = (res << 1) ^ int(c)
            next() # "0" or "1"
            first = 0
        return res
    def factor():
        c = read(cur)
        if c == "-":
            next() # "-"
            return -factor()
        elif c == "(":
            next() # "("
            val = expr()
            if read(cur) != ")":
                error()
            next() # ")"
            return val
        return number()
    def term():
        res = 1
        while 1:
            res *= factor()
            c = read(cur)
            if c != "*":
                break
            next() # "*"
        return res
    def expr():
        res = 0
        op = "+"
        while 1:
            if op == "+":
                res += term()
            else:
                res -= term()
            c = read(cur)
            if c not in "+-":
                break
            next() # "+" or "-"
            op = c
        return res
    lv = expr()
    next() # "="
    rv = expr()
    if not failed and cur == l:
        return lv == rv
    return 0

def get(b):
    def read(cur):
        if l <= cur:
            return "$"
        if s[cur] in base:
            return s[cur]
        return b[mapping[s[cur]]]
    return read

ans = 0
if cnt == 0:
    ans += solve(get(None))
for b in permutations(base, cnt):
    if "=" not in b or counter[b.index("=")] > 1:
        continue
    ans += solve(get(b))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
base = "=+-*()01"
s = input()
l = len(s)
mapping = {}
counter = {}
cnt = 0
for c in s:
    if c in base:
        continue
    if c not in mapping:
        mapping[c] = cnt
        cnt += 1
    v = mapping[c]
    counter[v] = counter.get(v, 0) + 1
if cnt > 8:
    print(0)
    exit(0)

def solve(read):
    cur = failed = 0
    def next():
        nonlocal cur
        cur += 1
    def error():
        nonlocal failed
        failed = 1
    def number():
        res = 0
        if read(cur) not in "01":
            error()
        first = 1
        while 1:
            c = read(cur)
            if c not in "01":
                break
            if not first and res == 0:
                error()
            res = (res << 1) ^ int(c)
            next() # "0" or "1"
            first = 0
        return res
    def factor():
        c = read(cur)
        if c == "-":
            next() # "-"
            return -factor()
        elif c == "(":
            next() # "("
            val = expr()
            if read(cur) != ")":
                error()
            next() # ")"
            return val
        return number()
    def term():
        res = 1
        while 1:
            res *= factor()
            c = read(cur)
            if c != "*":
                break
            next() # "*"
        return res
    def expr():
        res = 0
        op = "+"
        while 1:
            if op == "+":
                res += term()
            else:
                res -= term()
            c = read(cur)
            if c not in "+-":
                break
            next() # "+" or "-"
            op = c
        return res
    lv = expr()
    next() # "="
    rv = expr()
    if not failed and cur == l:
        return lv == rv
    return 0

def get(b):
    def read(cur):
        if l <= cur:
            return "$"
        if s[cur] in base:
            return s[cur]
        return b[mapping[s[cur]]]
    return read

ans = 0
if cnt == 0:
    ans += solve(get(None))
for b in permutations(base, cnt):
    if "=" in b and counter[b.index("=")] > 1:
        continue
    ans += solve(get(b))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
base = "=+-*()01"
s = input()
l = len(s)
mapping = {}
counter = {}
cnt = 0
for c in s:
    if c in base:
        continue
    if c not in mapping:
        mapping[c] = cnt
        cnt += 1
    v = mapping[c]
    counter[v] = counter.get(v, 0) + 1
if cnt > 8:
    print(0)
    exit(0)

def solve(read):
    cur = failed = 0
    def next():
        nonlocal cur
        cur += 1
    def error():
        nonlocal failed
        failed = 1
    def number():
        res = 0
        if read(cur) not in "01":
            error()
        first = 1
        while 1:
            c = read(cur)
            if c not in "01":
                break
            if not first and res == 0:
                error()
            res = (res << 1) ^ int(c)
            next() # "0" or "1"
            first = 0
        return res
    def factor():
        c = read(cur)
        if c == "-":
            next() # "-"
            return -factor()
        elif c == "(":
            next() # "("
            val = expr()
            if read(cur) != ")":
                error()
            next() # ")"
            return val
        return number()
    def term():
        res = 1
        while 1:
            res *= factor()
            c = read(cur)
            if c != "*":
                break
            next() # "*"
        return res
    def expr():
        res = 0
        op = "+"
        while 1:
            if op == "+":
                res += term()
            else:
                res -= term()
            c = read(cur)
            if c not in "+-":
                break
            next() # "+" or "-"
            op = c
        return res
    if sum(read(i) == "=" for i in range(l)) != 1:
        return 0
    lv = expr()
    next() # "="
    rv = expr()
    for i in range(l):
        print(end=read(i))
    print(" ", lv, rv, failed)
    if not failed and cur == l:
        return lv == rv
    return 0

def get(b):
    def read(cur):
        if l <= cur:
            return "$"
        if s[cur] in base:
            return s[cur]
        return b[mapping[s[cur]]]
    return read

ans = 0
for b in permutations(base, cnt):
    ans += solve(get(b))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
base = "=+-*()01"
s = input()
l = len(s)
mapping = {}
counter = {}
cnt = 0
for c in s:
    if c in base:
        continue
    if c not in mapping:
        mapping[c] = cnt
        cnt += 1
    v = mapping[c]
    counter[v] = counter.get(v, 0) + 1
if cnt > 8:
    print(0)
    exit(0)

def solve(read):
    cur = failed = 0
    def next():
        nonlocal cur
        cur += 1
    def error():
        nonlocal failed
        failed = 1
    def number():
        res = 0
        if read(cur) not in "01":
            error()
        first = 1
        while 1:
            c = read(cur)
            if c not in "01":
                break
            if not first and res == 0:
                error()
            res = (res << 1) ^ int(c)
            next() # "0" or "1"
            first = 0
        return res
    def factor():
        c = read(cur)
        if c == "-":
            next() # "-"
            return -factor()
        elif c == "(":
            next() # "("
            val = expr()
            if read(cur) != ")":
                error()
            next() # ")"
            return val
        return number()
    def term():
        res = 1
        while 1:
            res *= factor()
            c = read(cur)
            if c != "*":
                break
            next() # "*"
        return res
    def expr():
        res = 0
        op = "+"
        while 1:
            if op == "+":
                res += term()
            else:
                res -= term()
            c = read(cur)
            if c not in "+-":
                break
            next() # "+" or "-"
            op = c
        return res
    if sum(read(i) == "=" for i in range(l)) != 1:
        return 0
    lv = expr()
    next() # "="
    rv = expr()
    if not failed and cur == l:
        return lv == rv
    return 0

def get(b):
    def read(cur):
        if l <= cur:
            return "$"
        if s[cur] in base:
            return s[cur]
        return b[mapping[s[cur]]]
    return read

ans = 0
for b in permutations(base, cnt):
    ans += solve(get(b))
print(ans)