Problem:


Problem C: Verbal Arithmetic

Let's think about verbal arithmetic.

The material of this puzzle is a summation
of non-negative integers represented in a decimal format,
for example, as follows.

    905 +  125 = 1030

In verbal arithmetic, every digit appearing in the equation is masked with an alphabetic character.  A problem which has the above equation as one of its answers, for example, is the following.

    ACM + IBM = ICPC

Solving this puzzle means finding possible digit assignments
to the alphabetic characters in the verbal equation.

The rules of this puzzle are the following.

Each integer in the equation is expressed in terms of one or more
digits '0'-'9', but all the digits are masked with some alphabetic
characters 'A'-'Z'.

The same alphabetic character appearing in multiple places 
of the equation masks the same digit.
Moreover, all appearances of the same digit are masked with a single
alphabetic character.
That is, different alphabetic characters mean different digits.

The most significant digit must not be '0',
except when a zero is expressed as a single digit '0'.
That is, expressing numbers as "00" or "0123" is not permitted.

There are 4 different digit assignments for the verbal equation above
as shown in the following table.

MaskABCIMP

Case 1920153

Case 2930154

Case 3960157

Case 4970158

Your job is to write a program which solves this puzzle.

Input

The input consists of a number of datasets.
The end of the input is indicated by a line containing a zero.

The number of datasets is no more than 100.
Each dataset is formatted as follows.

N 

STRING 1 

STRING 2 

... 

STRING N 

The first line of a dataset contains an integer N  
which is the number of integers appearing in the equation.
Each of the following N   lines contains a string
composed of uppercase alphabetic characters 'A'-'Z'
which mean masked digits.

Each dataset expresses the following equation.

  STRING 1 + STRING 2 + ... + STRING N -1 = STRING N

The integer N   is greater than 2 and less than 13.
The length of STRING i is greater than 0
and less than 9.
The number of different alphabetic characters appearing 
in each dataset is greater than 0 and less than 11.

Output

For each dataset, output a single line containing 
the number of different digit assignments that satisfy the equation.

The output must not contain any superfluous characters.

Sample Input

3
ACM
IBM
ICPC
3
GAME
BEST
GAMER
4
A
B
C
AB
3
A
B
CD
3
ONE
TWO
THREE
3
TWO
THREE
FIVE
3
MOV
POP
DIV
9
A
B
C
D
E
F
G
H
IJ
0

Output for the Sample Input

4
1
8
30
0
0
0
40320



Sample input:
3
ACM
IBM
ICPC
3
GAME
BEST
GAMER
4
A
B
C
AB
3
A
B
CD
3
ONE
TWO
THREE
3
TWO
THREE
FIVE
3
MOV
POP
DIV
9
A
B
C
D
E
F
G
H
IJ
0


Sample output:
4
1
8
30
0
0
0
40320

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import permutations
import gc
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()

    n_coef_zero = 0
    coef_zero = []
    for ch, co in dd.items():
        if co < 0:
            break
        elif co==0:
            n_coef_zero += 1
            coef_zero.append(ch)
    else:
        if n_coef_zero!=len(dd):
            print(0)
            break

    gc.collect()
    ans = 0
    for t in permutations(range(10), r=len(dd)):
        sum_ = 0
        for v, (ch, co) in zip(t, dd.items()):
            if v == 0 and ch in non_zero:
                break
            else:
                sum_ += v * co
        else:
            ans += sum_ == 0

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import permutations
#import gc
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()

    n_coef_zero = 0
    coef_zero = []
    for ch, co in dd.items():
        if co < 0:
            break
        elif co==0:
            n_coef_zero += 1
            coef_zero.append(ch)
    else:
        if n_coef_zero!=len(dd):
            print(0)
            break

    #gc.collect()
    ans = 0
    for t in permutations(range(10), r=len(dd)):
        sum_ = 0
        for v, (ch, co) in zip(t, dd.items()):
            if v == 0 and ch in non_zero:
                break
            else:
                sum_ += v * co
        else:
            ans += sum_ == 0

    print(ans)

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**10
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(n):
        ss = [S() for _ in range(n)]
        cs = set()
        nz = set()
        for s in ss:
            cs |= set([c for c in s])
            if len(s) > 1:
                nz.add(s[0])
        l = len(cs)
        ci = {}
        cw = [0] * l
        for c,i in zip(sorted(list(cs), key=lambda x: 0 if x in nz else 1), range(l)):
            if c in nz:
                nz.add(i)
            ci[c] = i
        for s in ss[:-1]:
            w = 1
            for c in s[::-1]:
                cw[ci[c]] += w
                w *= 10
        w = 1
        for c in ss[-1][::-1]:
            cw[ci[c]] -= w
            w *= 10
        r = 0
        al = l // 2
        bl = l - al
        cwa = cw[:al]
        cwb = cw[al:]
        for _a in itertools.combinations(range(1, 10), al):
            ad = collections.defaultdict(int)
            bd = collections.defaultdict(int)
            for a in itertools.permutations(_a, al):
                tw = 0
                for i in range(al):
                    tw += cwa[i] * a[i]
                ad[tw] += 1
            _b = [_ for _ in range(1, 10) if _ not in _a]
            for b in itertools.permutations(_b, bl):
                tw = 0
                for i in range(bl):
                    tw += cwb[i] * b[i]
                bd[tw] += 1
            aa = sorted(ad.items())
            ba = sorted(bd.items(), reverse=True)
            aal = len(aa)
            bal = len(ba)
            ai = bi = 0
            while ai < aal and bi < bal:
                t = aa[ai][0] + ba[bi][0]
                if t == 0:
                    r += aa[ai][1] * ba[bi][1]
                    ai += 1
                    bi += 1
                elif t < 0:
                    ai += 1
                else:
                    bi += 1
        # print('ci', ci)
        # print('cw', cw)
        zl = [_ for _ in range(l) if _ not in nz][::-1]
        al = l - len(zl)
        bl = l - al
        if al == 0 or bl < 2:
            cws = [cw[i+1] - cw[i] for i in range(l-1)]
            for a in itertools.permutations(range(1, 10), l-1):
                tw = 0
                for i in range(l-1):
                    tw += cw[i] * a[i]
                zz = l - 1
                for zi in zl:
                    while zz > zi:
                        zz -= 1
                        tw += cws[zz] * a[zz]
                    if tw == 0:
                        r += 1
        else:
            cwa = cw[:al]
            cwb = cw[al:]
            # print('cwa', cwa)
            # print('cwb', cwb)
            zl = [_ - al for _ in zl]
            for _a in itertools.combinations(range(1, 10), al):
                ad = collections.defaultdict(int)
                bd = collections.defaultdict(int)
                for a in itertools.permutations(_a):
                    tw = 0
                    for i in range(al):
                        tw += cwa[i] * a[i]
                    ad[tw] += 1
                _b = [_ for _ in range(1, 10) if _ not in _a]
                cws = [cwb[i+1] - cwb[i] for i in range(bl-1)]
                for b in itertools.permutations(_b, bl-1):
                    tw = 0
                    for i in range(bl-1):
                        tw += cwb[i] * b[i]
                    zz = bl - 1
                    for zi in zl:
                        while zz > zi:
                            zz -= 1
                            tw += cws[zz] * b[zz]
                        bd[tw] += 1
                aa = sorted(ad.items())
                ba = sorted(bd.items(), reverse=True)
                aal = len(aa)
                bal = len(ba)
                ai = bi = 0
                while ai < aal and bi < bal:
                    t = aa[ai][0] + ba[bi][0]
                    if t == 0:
                        r += aa[ai][1] * ba[bi][1]
                        ai += 1
                        bi += 1
                    elif t < 0:
                        ai += 1
                    else:
                        bi += 1
        return r

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        # print(rr[-1])

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



print(main())

Submission status: Runtime Error

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**10
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(n):
        ss = [S() for _ in range(n)]
        cs = set()
        nz = set()
        for s in ss:
            cs |= set([c for c in s])
            if len(s) > 1:
                nz.add(s[0])
        l = len(cs)
        ci = {}
        cw = [0] * l
        for c,i in zip(cs, range(l)):
            ci[c] = i
            if c in nz:
                nz.add(i)
        for s in ss[:-1]:
            w = 1
            for c in s[::-1]:
                cw[ci[c]] += w
                w *= 10
        w = 1
        for c in ss[-1][::-1]:
            cw[ci[c]] -= w
            w *= 10
        r = 0
        lnz = l-1 not in nz
        cw1 = cw[-1]
        for a in itertools.permutations(range(10), l-1):
            if 0 in a and a.index(0) in nz:
                continue
            tw = 0
            for i in range(l-1):
                tw += cw[i] * a[i]
            if tw == 0:
                if cw1 == 0:
                    for i in range(1, 10):
                        if i not in a:
                            r += 1
                if lnz and 0 not in a:
                    r += 1
                continue
            if cw1 == 0 or tw % cw1:
                continue
            tk = -tw // cw1
            if 0 < tk < 10 and tk not in a:
                r += 1
        return r

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

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



print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import permutations
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()
    ans = 0
    for t in permutations(range(10), r=len(dd)):
        sum_=0
        for i, (v, (ch, co)) in enumerate(zip(t, dd.items())):
            if v==0 and ch in non_zero:
                break
            else:
                sum_ += v*co
        else:
            if sum_==0:
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import permutations
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()
    ans = 0
    for t in permutations(range(10), r=len(dd)):
        sum_=0
        for v, (ch, co) in zip(t, dd.items()):
            if v==0 and ch in non_zero:
                break
            else:
                sum_ += v*co
        else:
            if sum_==0:
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:

from collections import defaultdict
from itertools import permutations
import gc
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()

    n_coef_zero = 0
    coef_zero = []
    for ch, co in dd.items():
        if co < 0:
            break
        elif co==0:
            n_coef_zero += 1
            coef_zero.append(ch)
    else:
        if n_coef_zero!=len(dd):
            print(0)
            continue

    gc.collect()
    ans = 0
    for t in permutations(range(10), r=len(dd)):
        sum_ = 0
        for v, (ch, co) in zip(t, dd.items()):
            if v == 0 and ch in non_zero:
                break
            else:
                sum_ += v * co
        else:
            ans += sum_ == 0

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import permutations
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()

    n_coef_zero = 0
    coef_zero = []
    for ch, co in dd.items():
        if co < 0:
            break
        elif co==0:
            n_coef_zero += 1
            coef_zero.append(ch)
    else:
        if n_coef_zero!=len(dd):
            print(0)
            continue

    ans = 0
    dditems = list(dd.items())

    for t in permutations(range(10), r=len(dd)):
        sum_ = 0
        for v, (ch, co) in zip(t, dditems):
            if v == 0 and ch in non_zero:
                break
            else:
                sum_ += v * co
        else:
            ans += sum_ == 0

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import permutations
while True:
    N = int(input())
    if N==0:
        break

    non_zero = set()
    dd = defaultdict(int)
    for _ in range(N-1):
        s = input()
        for i, c in enumerate(s[::-1]):
            dd[c] += 10**i
        if len(s) != 1:
            non_zero.add(s[0])
    s = input()
    for i, c in enumerate(s[::-1]):
        dd[c] -= 10 ** i
    if len(s) != 1:
        non_zero.add(s[0])

    #char = dd.keys()
    #coef = dd.values()

    n_coef_zero = 0
    coef_zero = []
    for ch, co in dd.items():
        if co < 0:
            break
        elif co==0:
            n_coef_zero += 1
            coef_zero.append(ch)
    else:
        if n_coef_zero!=len(dd):
            print(0)
            continue

    ans = 0
    dditems = list(dd.items())

    for t in permutations(range(10), r=len(dditems)):
        sum_ = 0
        for v, (ch, co) in zip(t, dditems):
            if v == 0 and ch in non_zero:
                break
            else:
                sum_ += v * co
        else:
            ans += sum_ == 0

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
def solve(n, S):
    C = {}; E = {}
    for i, s in enumerate(S):
        v = 1
        for c in reversed(s):
            if c not in C:
                C[c] = 1
            if i < n-1:
                E[c] = E.get(c, 0) + v
            else:
                E[c] = E.get(c, 0) - v
            v *= 10
        if len(s) > 1:
            C[s[0]] = 0
    K = sorted(C, key=lambda x: C[x])
    def dfs(c, D):
        if c == len(K):
            return sum(D.values()) == 0
        res = 0
        k = K[c]
        for i in range(10-c):
            v = deq.popleft()
            if v or C[k]:
                D[k] = v * E[k]
                res += dfs(c+1, D)
            deq.append(v)
        return res
    return dfs(0, {})
deq = deque(range(10))
while 1:
    n = int(input())
    if n == 0:
        break
    S = [input() for i in range(n)]
    print(solve(n, S))