动画取自维基百科
小巧和小克在中文课时下四子棋。四子棋规矩如下:
- 棋盘竖立,有 $ 7 $ 行 $ 6 $ 列共 $ 42 $ 个位置,行从左到右以 $ 1 ∼ 7 $ 编号。开局时棋盘没有棋子。
- 玩家轮流下一步棋:选择一行投下一枚己方棋子,棋子落在该行最低未占位置。 一行满 $ 6 $ 枚棋则不能选择该行。
- 当一方 $ 4 $ 枚棋子以纵、横、斜其中一个方向连成一线时,该方获胜,棋局终止。
- 当棋盘满棋而没有一方获胜,则平手,棋局终止。
小巧带了棋盘回校,却忘了棋子在家。恰好是巧克力金币节,每位学生获赠 $ 21 $ 枚巧克力金币,两人金币正好能用作棋子。
小巧和小克分别在自己金币上作 x
和 o
记号以辨识。
他们约定,赢家能把两人所有金币带回家,平手则一起向中文老师投掷金币。
抛巧克力金币,决定了小巧是先手,因此若 $ i $ 是单数,第 $ i $ 步棋由小巧下,否则由小克下。 以 $ c_i $ 表示第 $ i $ 步投下棋子那一行的编号。 小巧和小克轮流下了共 $ n $ 步棋后,中文老师要小克作免费劳动,到十七楼的教员室拿作业。 在这期间,小巧偷偷继续游戏,下自己的棋之余代小克下棋,下了双方共 $ m $ 步棋。 注意双方的棋子仍然轮流下,不会有连续两步棋属同一方。
现在请你判断,小巧有没有可能刚下完第 $ n + m $ 步棋时自己获胜(棋局到这步棋才终止)? 如有,依次输出小克离开后,使小巧胜出的任何 $ m $ 步棋 $ c_{n+1}, c_{n+2}, \cdots, c_{n+m} $。
输入格式
第一行两个整数 $ n, m $。
第二行 $ n $ 个整数 $ c_1, c_2, \cdots, c_n $。保证下了首 $ n $ 步棋后棋局未终止。
输出格式
如果能小巧在上述条件下获胜,第一行输出 Yes
,
第二行输出 $ m $ 个用空格隔开的整数 $ c_{n+1}, c_{n+2}, \cdots, c_{n+m} $。
否则,仅输出一行 No
。
数据范围
对于 $ 30\% $ 的数据:$ m = 1 $
对于 $ 100\% $ 的数据:$ 1 \le n \le 40; 1 \le m \le \min(41 - n, 6); n + m $ 是单数$ ; 1 \le c_i \le 7 $
Sample Test Cases
Input | Output | |
---|---|---|
6 1 3 4 3 4 3 4 |
Yes 3 |
|
刚下了第 $ n $ 步的棋盘: ....... ....... ....... ..xo... ..xo... ..xo... 小巧在第三行投下一枚棋子便获胜。 |
||
9 4 4 3 2 1 3 2 2 1 1 |
Yes 7 7 7 1 |
|
刚下了第 $ n $ 步的棋盘: ....... ....... ....... xx..... oox.... oxox...
小巧不能在第 $ 11 $ 步在第 $ 1 $ 行投下棋子胜出,因为这令棋局未达第 $ n + m $ 步已终止。
....... ....... x...... xx....o oox...x oxox..o |
||
1 2 6 |
No |
Scoring: Per Case
Authored by s16f22
Appeared in 2021 SDIC 练习