/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
整数 N,K 及び長さ N の数列 A=(A_1,\ldots,A_N) が与えられます．
A に対し以下の操作を 500000 回以下行うことで A を広義単調増加にできるか判定し，可能な場合は実際に操作手順を一つ示してください．
- 1 以上 N-1 以下の整数 i を選ぶ．A_i を A_{i+1}+K で，A_{i+1} を A_i で同時に置き換える．
制約
- 入力される数値は全て整数
- 2 \leq N \leq 50
- 1\leq K \leq 50
- 1\leq A_i\leq 50
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 \ldots A_N
出力
500000 回以下の操作で A を広義単調増加にできない場合 No を出力せよ．広義単調増加にできる場合，操作回数を M\ (0 \leq M \leq 500000) とし，k 回目 (1\leq k \leq M) の操作で選んだ i を i_k として以下の形式で出力せよ．
Yes M i_1 \ldots i_M
条件を満たす解が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
3 2 3 6 4
出力例 1
Yes 1 2
i=2 として操作を行います．A_2 を A_3+2=6 で，A_3 を A_2=6 で同時に置き換えるので，操作後の A は A=(3,6,6) となります．
これにより A は広義単調増加になっているので，この出力は条件を満たします．
入力例 2
3 3 1 5 8
出力例 2
Yes 2 2 2
操作回数を最小化する必要はありません．
Score : 600 points
Problem Statement
You are given integers N, K, and a sequence A = (A_1, \ldots, A_N) of length N.
Determine whether it is possible to make A non-decreasing by performing the following operation at most 500000 times, and if possible, provide one sequence of operations to do so.
- Choose an integer i between 1 and N-1, inclusive. Simultaneously replace A_i with A_{i+1} + K, and A_{i+1} with A_i.
Constraints
- All input numbers are integers.
- 2 \leq N \leq 50
- 1 \leq K \leq 50
- 1 \leq A_i \leq 50
Input
The input is given from Standard Input in the following format:
N K A_1 \ldots A_N
Output
If it is impossible to make A non-decreasing within 500000 operations, print No. Otherwise, print a solution in the following format, where M is the number of operations (0 \leq M \leq 500000), and i_k is the i chosen in the k-th operation (1 \leq k \leq M):
Yes M i_1 \ldots i_M
If multiple valid solutions exist, any of them will be considered correct.
Sample Input 1
3 2 3 6 4
Sample Output 1
Yes 1 2
Let us perform the operation with i=2. This simultaneously replaces A_2 with A_3 + 2 = 6, and A_3 with A_2 = 6, making A = (3,6,6).
Now A is non-decreasing, so this output satisfies the conditions.
Sample Input 2
3 3 1 5 8
Sample Output 2
Yes 2 2 2
It is not necessary to minimize the number of operations.