/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
問題文
数字と ? からなる長さ N の文字列 S が与えられます。
全ての ? を数字に置き換えて以下の値を 10 の倍数にすることができるか判定し、可能な場合は ? の置き換え方を 1 通り求めてください。
- \displaystyle \sum^{N}_{i=1} i \times ( S の i 文字目を 1 桁の整数とみなした時の値 )
制約
- N は 1 以上 2 \times 10^5 以下の整数
- S は数字と
?からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
問題文中の条件を満たす置き換え方が存在しない場合、 No と 1 行に出力してください。
そうでない場合、以下の形式に従い置き換え方を出力してください。
Yes T
まず、 1 行目に Yes と出力してください。
次に、 2 行目に ? を問題文中の条件を満たすように置き換えた文字列 T を出力してください。
入力例 1
5 935?0
出力例 1
Yes 93550
935?0 の 4 文字目の ? を置き換えることを考えます。
- 4 文字目の
?を 5 に置き換えた時、置き換えた後の文字列は T=93550となります。- 1 \times 9 + 2 \times 3 + 3 \times 5 + 4 \times 5 + 5 \times 0 = 50 となり、これは確かに 10 の倍数です。
他にも、 4 文字目の ? を 0 に置き換えた 93500 も問題文中の条件を満たします。
入力例 2
5 1?3?5
出力例 2
No
1?3?5 の 2 つの ? を数字に置き換える方法は全部で 100 通りありますが、どのように置き換えても問題文中の条件を満たすことができません。
入力例 3
1 0
出力例 3
Yes 0
文字列 0 は置き換えるべき ? を含みませんが、 1 \times 0 = 0 は元々 10 の倍数です。
Problem Statement
You are given a length-N string S consisting of digits and ?.
Determine if one can replace each occurrence of ? with a digit so that the following value is a multiple of 10. If it is possible, find one such replacement.
- \displaystyle \sum^{N}_{i=1} i \times (the i-th character of S interpreted as a one-digit integer).
Constraints
- N is an integer between 1 and 2 \times 10^5, inclusive.
- S is a length-N string consisting of digits and
?.
Input
The input is given from Standard Input in the following format:
N S
Output
Print No in a single line if there is no conforming replacement.
Otherwise, print a replacement in the following format.
Yes T
The first line should contain Yes.
The second line should contain a string T obtained by a replacement that satisfies the condition in the problem statement.
Sample Input 1
5 935?0
Sample Output 1
Yes 93550
Consider what digit should replace the 4-th character ? of 935?0.
- If the 4-th character
?is replaced by 5, the resulting string is T=93550.- 1 \times 9 + 2 \times 3 + 3 \times 5 + 4 \times 5 + 5 \times 0 = 50, which is indeed a multiple of 10.
Alternatively, we can also satisfy the condition in the problem statement by replacing the 4-th character ? with 0, thus yielding 93500.
Sample Input 2
5 1?3?5
Sample Output 2
No
There are 100 ways to replace the two occurrences of ? in 1?3?5, but none of them satisfies the condition in the problem statement.
Sample Input 3
1 0
Sample Output 3
Yes 0
While the string 0 does not contain ? to replace, 1 \times 0 = 0 is already a multiple of 10.