Codeforces School Team Contest #2 H. 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