Codeforces School Team Contest #2 H. Phone Number

Phone Number

動的計画法。i番目の数字がjであるときi番目以降に何通りの電話番号があるかを記憶しておく。Masha自身の番号が生成可能なら-1。

d = [int(x) for x in raw_input()]
n = len(d)
T = [[0]*10 for x in range(n)]
T[n-1] = [1]*10
for i in range(n-2,-1,-1):
    for j in range(10):
        if (j+d[i+1])%2==0:
            T[i][j] = T[i+1][(j+d[i+1])/2]
        else:
            T[i][j] = T[i+1][(j+d[i+1])/2]+T[i+1][(j+d[i+1])/2+1]
# check Masha's number
f = 1
for i in range(1,n):
    if (d[i]+d[i-1])%2==0:
        if d[i]!=(d[i]+d[i-1])/2:
            f = 0
    else:
        if d[i]!=(d[i]+d[i-1])/2 and d[i]!=(d[i]+d[i-1])/2+1:
            f = 0
    
print sum(T[0])-f