CS Academy Round #39: C. Reconstruct Sum

入力の与えられる向きに関する英語が難しい。

solution

繰り上がりの状況は固定されているので各桁は完全に独立。 それぞれ個数を数え足し合わせる。 $O(\log S)$。

implementation

#!/usr/bin/env python3
s = int(input())
log_s = len(str(s))
is_carried = list(map(int, input().split())) + [ 0 ]
digits = list(map(int, reversed(str(s))))
result = 1
for i in range(log_s):
    c = (i - 1 >= 0 and is_carried[i - 1])
    cnt = 0
    for a in range(10):
        b = digits[i] - a - c
        cnt += bool(b < 0) == bool(is_carried[i])
    result *= cnt
print(result)