102571: [AtCoder]ABC257 B - 1D Pawn
Description
Score : $200$ points
Problem Statement
There are $N$ squares, indexed Square $1$, Square $2$, …, Square $N$, arranged in a row from left to right.
Also, there are $K$ pieces. The $i$-th piece from the left is initially placed on Square $A_i$.
Now, we will perform $Q$ operations against them.
The $i$-th operation is as follows:
- If the $L_i$-th piece from the left is on its rightmost square, do nothing.
- Otherwise, move the $L_i$-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.
Print the index of the square on which the $i$-th piece from the left is after the $Q$ operations have ended, for each $i=1,2,\ldots,K$.
Constraints
- $1\leq K\leq N\leq 200$
- $1\leq A_1<A_2<\cdots<A_K\leq N$
- $1\leq Q\leq 1000$
- $1\leq L_i\leq K$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $Q$ $A_1$ $A_2$ $\ldots$ $A_K$ $L_1$ $L_2$ $\ldots$ $L_Q$
Output
Print $K$ integers in one line, with spaces in between. The $i$-th of them should be the index of the square on which the $i$-th piece from the left is after the $Q$ operations have ended.
Sample Input 1
5 3 5 1 3 4 3 3 1 1 2
Sample Output 1
2 4 5
At first, the pieces are on Squares $1$, $3$, and $4$. The operations are performed against them as follows:
- The $3$-rd piece from the left is on Square $4$. This is not the rightmost square, and the next square on the right does not contain a piece, so move the $3$-rd piece from the left to Square $5$. Now, the pieces are on Squares $1$, $3$, and $5$.
- The $3$-rd piece from the left is on Square $5$. This is the rightmost square, so do nothing. The pieces are still on Squares $1$, $3$, and $5$.
- The $1$-st piece from the left is on Square $1$. This is not the rightmost square, and the next square on the right does not contain a piece, so move the $1$-st piece from the left to Square $2$. Now, the pieces are on Squares $2$, $3$, and $5$.
- The $1$-st piece from the left is on Square $2$. This is not the rightmost square, but the next square on the right (Square $3$) contains a piece, so do nothing. The pieces are still on Squares $2$, $3$, and $5$.
- The $2$-nd piece from the left is on Square $3$. This is not the rightmost square, and the next square on the right does not contain a piece, so move the $2$-nd piece from the left to Square $4$; Now, the pieces are still on Squares $2$, $4$, and $5$.
Thus, after the $Q$ operations have ended, the pieces are on Squares $2$, $4$, and $5$, so $2$, $4$, and $5$ should be printed in this order, with spaces in between.
Sample Input 2
2 2 2 1 2 1 2
Sample Output 2
1 2
Sample Input 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
Sample Output 3
2 5 6 7 9 10
Input
题意翻译
有$N$个格子,从左到右编号为$1, 2, \dots, N$。 有$K$张卡片, 从左到右的第$i$张卡片放在$A_i$个格子里。 现在,有$Q$次操作,第$i$次查询对应的整数为$L_i$, 意义如下所示: + 如果第$L_i$张卡片在最右边的格子里,什么也不做。 + 否则,将第$L_i$张卡片往右边移动一格,如果它右边没有卡片的话。 输出最后每一张卡片的位置。Output
分数:$200$分
问题描述
有$N$个方格,按照从左到右的顺序编号为 Square $1$,Square $2$,…,Square $N$。
此外,有$K$个棋子。最左边的第$i$个棋子初始放置在 Square $A_i$。
现在,我们要对它们进行$Q$次操作。
第$i$次操作如下:
- 如果从左边数的第$L_i$个棋子在其最右侧的方格上,则什么也不做。
- 否则,如果右边相邻的方格上没有棋子,将从左边数的第$L_i$个棋子向右移动一个方格;否则,什么也不做。
在进行完$Q$次操作后,对于每$i=1,2,\ldots,K$,输出从左边数的第$i$个棋子所在的方格的编号。
限制条件
- $1\leq K\leq N\leq 200$
- $1\leq A_1<A_2<\cdots<A_K\leq N$
- $1\leq Q\leq 1000$
- $1\leq L_i\leq K$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出,格式如下:
$N$ $K$ $Q$ $A_1$ $A_2$ $\ldots$ $A_K$ $L_1$ $L_2$ $\ldots$ $L_Q$
输出
在一行中打印$K$个整数,之间用空格隔开。 第$i$个整数应该是进行完$Q$次操作后,从左边数的第$i$个棋子所在的方格的编号。
样例输入 1
5 3 5 1 3 4 3 3 1 1 2
样例输出 1
2 4 5
起始时,棋子在Squares $1$,$3$和$4$上。按照以下方式对它们进行操作:
- 从左边数的第$3$个棋子在Square $4$上。 这不是最右侧的方格,且右边相邻的方格上没有棋子,所以将从左边数的第$3$个棋子移动到Square $5$。 现在,棋子在Squares $1$,$3$和$5$上。
- 从左边数的第$3$个棋子在Square $5$上。 这是最右侧的方格,所以什么也不做。 棋子仍然在Squares $1$,$3$和$5$上。
- 从左边数的第$1$个棋子在Square $1$上。 这不是最右侧的方格,且右边相邻的方格上没有棋子,所以将从左边数的第$1$个棋子移动到Square $2$。 现在,棋子在Squares $2$,$3$和$5$上。
- 从左边数的第$1$个棋子在Square $2$上。 这不是最右侧的方格,但右边相邻的方格(Square $3$)上有一个棋子,所以什么也不做。 棋子仍然在Squares $2$,$3$和$5$上。
- 从左边数的第$2$个棋子在Square $3$上。 这不是最右侧的方格,且右边相邻的方格上没有棋子,所以将从左边数的第$2$个棋子移动到Square $4$; 现在,棋子仍然在Squares $2$,$4$和$5$上。
因此,在进行完$Q$次操作后,棋子在Squares $2$,$4$和$5$上,因此应按顺序打印$2$,$4$和$5$,之间用空格隔开。
样例输入 2
2 2 2 1 2 1 2
样例输出 2
1 2
样例输入 3
10 6 9 1 3 5 7 8 9 1 2 3 4 5 6 5 6 2
样例输出 3
2 5 6 7 9 10