Problem:


Problem A : ID

A大学ではIDの入力ミスが多発していた。

そこで、A大学は入力ミス防止のため新しいIDを発行することにした。

新しいIDには入力ミス防止のためにIDが正しいかどうかチェックする方法がある。

・全ての桁の数字の総和を求める。

・ただし、右端の桁を１番目として、偶数番目の桁の数字を２倍にする。

・２倍することによって数字が１０以上になった時、１の位の数字と１０の位の数字を加算した数字をその桁の数字とする。

・総和が１０で割り切れれば正しいID、そうでなければ間違いとする。

例として、53579というIDをチェックする。

全ての桁の数字の総和を求めるので、

5 + 3 + 5 + 7 + 9

ただし、偶数番目の桁の数字を２倍にするので、

5 + 6 + 5 + 14 + 9

２倍することによって数字が１０以上になった時、１の位の数字と１０の位の数字を加算した数字をその桁の数字とするので、

5 + 6 + 5 + (1 + 4) + 9

以上より、総和は30となる。30は10で割り切れるので、53579は正しいIDである。

B君はA大学の大学生であり、新しいIDを発行してもらったが、IDの一部の桁を忘れてしまった。

しかし、忘れてしまった部分にどんな数字が入るか、いくつか候補を絞ることに成功した。

あなたの仕事は、B君のIDの正しい組み合わせが何通りあるかを求めることである。

Input

入力は以下のフォーマットで与えられる。

n
ID
m
a0 a1 ... am-1

nはIDの桁の数である。

IDの各桁には0~9の数字または忘れた桁であるということを示す'*'という文字が入る。

mは'*'に入る数字の候補の数である。

aiは'*'に入る数字の候補である。

入力は以下の制約を満たす

1 ≤ n ≤ 100,000

1 ≤ m ≤ 10

0 ≤ ai ≤ 9

1 ≤ '*'の数 ≤ 7

Output

答えの値を１行に出力せよ

Sample Input 1

5
5*57*
2
3 9

Sample Output 1

1

Sample Input 2

15
2***9*2*6*1199*
9
0 1 2 3 4 6 7 8 9

Sample Output 2

478297



Sample input:
5
5*57*
2
3 9


Sample output:
1

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
id = input()[::-1]
count = 0
a = []
odd, even = 0 , 0
tmp = 0
for i in range(1,n+1):
    if id[i-1] == "*":
        if i % 2:
            odd += 1
        else:
            even += 1
        continue
    if i % 2:
        x = int(id[i-1])
        if x >= 5:
            tmp += (int(id[i-1]) * 2 - 9)
            continue
        tmp += (int(id[i-1]) * 2 - 9)
    tmp += (int(id[i-1]))
m = int(input())

data = list(map(int, input().split()))

def sum2(ls):
    ans = 0
    for k in ls:
        if k >= 5:
            ans += (k * 2 - 9)
        else:
            ans += (k * 2)
    return ans

odd_list = list(map(lambda x: (sum(x) % 10),list(itertools.product(data, repeat=odd))))
even_list = list(map(lambda x: ((sum2(x)) % 10),list(itertools.product(data, repeat=even))))
odd_mod = [odd_list.count(i) for i in range(10)]
even_mod = [even_list.count(i) for i in range(10)]
for i in range(10):
    for j in range(10):
        if ((i + j + tmp) % 10) == 0:
            count += odd_mod[i] * even_mod[j]

print(count)

Submission status: Time Limit Exceeded

Solution code:
# Edit: 2014/09/07
# Lang: Python3
# Time: s

from itertools import product


def judge(n, id):
    sum = 0
    for i in range(1, n + 1):
        # print(id[-i])
        if i % 2 == 0:
            s = int(id[-i]) * 2
            if s > 10:
                s = s % 10 + 1
            sum += s
        else:
            sum += int(id[-i])
    #print(sum, sum % 10)
    if sum % 10:
        return False
    else:
        return True


if __name__ == "__main__":
    n = int(input())
    ID = list(input())
    m = int(input())
    alist = list(map(int, input().strip("\n").split(" ")))

    # print("n    :", n)
    #print("ID   :", ID)
    #print("m    :", m)
    #print("alist:", alist)

    # id = 12345
    # print(judge(len(str(id)), str(id)))
    # id = 53579
    # print(judge(len(str(id)), str(id)))

    ast = []  # *の位置を検出
    for i in range(n):
        if ID[i] == "*":
            ast.append(i)
    #print("ast", ast)

    #ID[0] = "3"
    #print("ID[0]",ID[0])
    """
    for x, y in product(alist, repeat=len(ast)):
        print(x, y)
        ID[int(ast[0])] = str(x)
        ID[int(ast[1])] = str(y)
        print(ID)
        print(judge(n, ID))
    """
    ilist = []
    nTrue = 0
    for ilist in product(alist, repeat=len(ast)):
        #print(ilist)
        for iast in range(len(ast)):
            ID[ast[iast]] = ilist[iast]
        #print("ID",ID)

        #for v in ast:
        #    ID[v] = *** #from alist
        nTrue += judge(n, ID)
    print(nTrue)
pass
#

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
n = int(raw_input())
ID = raw_input()
m = int(raw_input())
a = raw_input().split()

def is_right_digit(id_num):
    """String id_num
    return True or False"""
    tmp = 0
    tot = int(id_num[-1])
    for i in reversed(xrange(1,n)):
        if i%2==0 and int(id_num[i])*2>=10:
            t = int(id_num[i])*2
            tmp = int(str(t)[0]) + int(str(t)[1])
            tot += tmp
        elif i%2==0 and int(id_num[i])*2<10:
            tot = int(id_num[i])
        else:
            tot += int(id_num[i])
    if tot%10==0:
        return True
    else:
        return False
        
def perm(ID,n):
    cnt = 0
    ast_pos = []
    for i in xrange(n):
        if ID[i]=="*":
            ast_pos.append(str(i))
            
    for elem in itertools.product(a, repeat=len(ast_pos)):
        # ("0","0","9",...)
        id_num = ""
        ast_i = 0
        for i in range(n):
            if ID[i]!="*":
                id_num += ID[i]
            else:
                id_num += elem[ast_i]
                ast_i += 1
        if is_right_digit(id_num):
            cnt += 1
    print cnt
    
perm(ID,n)

Submission status: Time Limit Exceeded

Solution code:
import itertools
r=[0,2,4,6,8,1,3,5,7,9]
def isId(Id,comb):
	id=Id[:]
	for i in comb:
		id[id.index("*")]=i
	s=0
	for i in range(1,len(id)+1):
		if i%2==1:
			s+=int(id[-i])
		else:
			s+=r[int(id[-i])]
	return True if s%10==0 else False
	
n=input()
id=list(raw_input())
l=id.count("*")
m=input()
num=raw_input().replace(" ","")
ans=0
for comb in itertools.product(num,repeat=l):
	if isId(id,comb):
		ans+=1
print ans

Submission status: Accepted

Solution code:
def fun(Z,z):
    for i in range(z-1):
        for j in range(10):
            for p in range(10):
                q=(j-p)%10
                Z[i+1][j]+=Z[i][p]*Z[0][q]
    return Z

N=int(raw_input())
I=raw_input()
d=0
e=0
s=0
for i in range(1, N+1):
    if I[-i]=='*':
        if i%2: d+=1
        else:   e+=1
    else:
        k=int(I[-i])
        if i%2: s+=k
        else:   s+= (k*2)/10 + (k*2)%10
req=(10-s%10)%10
m=int(raw_input())
A=map(int, raw_input().split())
B=map(lambda x: (x*2)/10 + (x*2)%10, A)
D=[[0 for i in range(10)] for j in range(d)]
E=[[0 for i in range(10)] for j in range(e)]
if d>0:
    for i in A:
        D[0][i]=1
if e>0:
    for i in B:
        E[0][i]=1

D=fun(D,d)
E=fun(E,e)
ans=0
for i in range(10):
    if d>0 and e>0:
        j=(req-i)%10
        ans+=D[-1][i]*E[-1][j]
    elif d>0:
        ans=D[-1][req]
    else:
        ans=E[-1][req]
print ans

Submission status: Accepted

Solution code:
import itertools

n = int(input())
id = input()[::-1]
count = 0
a = []
odd, even = 0 , 0
tmp = 0
for i in range(1,n+1):
    if id[i-1] == "*":
        if i % 2:
            odd += 1
        else:
            even += 1
    elif i % 2 == 0:
        x = int(id[i-1])
        if x >= 5:
            tmp += (x * 2 - 9)
        else:
            tmp += (x * 2)
    else:
        tmp += (int(id[i-1]))
m = int(input())

data = list(map(int, input().split()))

def sum2(ls):
    ans = 0
    for k in ls:
        if k >= 5:
            ans += (k * 2 - 9)
        else:
            ans += (k * 2)
    return ans

odd_list = list(map(lambda x: (sum(x) % 10),list(itertools.product(data, repeat=odd))))
even_list = list(map(lambda x: ((sum2(x)) % 10),list(itertools.product(data, repeat=even))))
odd_mod = [odd_list.count(i) for i in range(10)]
even_mod = [even_list.count(i) for i in range(10)]
for i in range(10):
    for j in range(10):
        if ((i + j + tmp) % 10) == 0:
            count += odd_mod[i] * even_mod[j]

print(count)

Submission status: Accepted

Solution code:
n = int(input())
ID = input()[::-1]
m = int(input())
a_lst = list(map(int, input().split()))
dp = [[0] * 10 for _ in range(n + 1)]
dp[0][0] = 1


def fix(a):
    if a < 10:return a
    return a % 10 + a // 10


for i in range(n):
    c = ID[i]
    mag = 1 if i % 2 == 0 else 2
    for j in range(10):
        if c == "*":
            for a in a_lst:
                a = fix(a * mag)
                dp[i + 1][(j + a) % 10] += dp[i][j]
        else:
            a = fix(int(c) * mag)
            dp[i + 1][(j + a) % 10] += dp[i][j]
print(dp[n][0])