writerのharurun君は以下の問題「Digit Sum」を考え、問題セットに追加しようとしていました。
正整数 $N$ の各桁の総和を $f(N)$ と表します。
正整数 $K$、$Y$ が与えられます。以下の条件をすべて満たす正整数 $X$ を $1$ つ求めてください。
- $X$ の桁数は $K$ である。
- $X$ のいずれの桁も $0$ ではない。
- $f^{(10^{100})}(X)=Y$ である。ただし、$f^{(10^{100})}(X)$ は $X$ に $f$ を $10^{100}$ 回反復適用したものを表す。
しかしながら、adminのharurun君はこの問題は簡単だと考え、次のように強化してしまいました。 以下の問題文に書かれている問題を解いてください。
正整数 $N$ の各桁の総和を $f(N)$ と表します。厳密には $f(N)=\sum_{i=0}^{\infty}\left(\lfloor N/10^i\rfloor \bmod 10\right)$ と定義します。
正整数 $K$、$Y$、および長さ $9$ の 0 と 1 からなる文字列 $S$ が与えられます。
以下の条件をすべて満たす正整数 $X$ が存在するならば Yes、存在しないならば No を出力してください。
1 であるような整数 $i$ のいずれかである。$T$ 個のテストケースが与えられるので、それぞれについて解いてください。
0,1 からなる文字列1 であるような $1$ 以上 $9$ 以下の $i$ が必ず存在入力は以下の形式で標準入力から与えられます。
$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$
ただし、 $case_i$ は $i$ 個目のテストケースを表し、以下の形式で与えられます。
$K$ $Y$ $S$
全体で $T$ 行出力してください。
$i$ 行目には $i$ 個目のテストケースに対して、$X$ が存在するならば Yes、存在しないならば No を出力してください。
4 3 1 001100000 65 9 111111111 100 12 001001001 1000000000 2 100100100
Yes Yes No No
$1$ つ目のテストケースについて、例えば $X=334$ が条件を満たします。 $f(334)=10$ であり、 $f(10)=1$ となります。 さらに、$f(1)=1$ であるため、 $f(f(f(f(334))))=1$ となり条件を満たします。
$2$ つ目のテストケースについて、例えば $X=45^{39}$ が条件を満たします。