AtCoder Regular Contest 187
翻译中…
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.
翻译中…
样例
Input #1
3 2
3 6 4
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.
Input #2
3 3
1 5 8
Output #2
Yes
2
2 2
It is not necessary to minimize the number of operations.
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。