← 返回题目列表

AtCoder · arc195_c

C. 哈密顿件

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一块板 10^9 行和 10^9 列,以及 R 红色碎片和 B 蓝色碎片。在这里, R+B 不小于 2。广场位于 r从顶部算起的第行和 c从左边算起的第列称为正方形 (r,c)。红色棋子可以一步垂直或水平移动一格,蓝色棋子可以一步对角移动一格。更准确地说,正方形上的红色棋子 (r,c) 可以移至 (r+1,c), (r,c+1), (r-1,c), (r,c-1) 如果目标方格存在,且方格上有蓝色棋子,则一举 如果目标方格存在,则一举 (r,c) 可以移至 (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) 。

我们想把所有 (R+B) 棋盘上的棋子可以任意顺序,一一对应,但需满足以下条件:

  • 一个方格上最多放置一个棋子。
  • 对于每个 i (1 \leq i \leq R+B-1), i放置的第一个棋子可以一步移动到包含该棋子的方格 (i+1)已放置第 块。
  • 的 (R+B)放置的第一个棋子可以一步移动到包含该棋子的方格 1-放置了第一块。

确定是否有办法放置 (R+B) 满足这些条件的件。如果存在,请显示一个示例。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\leq T\leq 10^5
  • 0 \leq R, B
  • 2 \leq R + B \leq 2 \times 10^5
  • 总和 (R+B) 所有测试用例最多 2\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出:

R B

输出

按顺序打印每个测试用例的答案,以换行符分隔。

如果无法放置满足测试用例条件的棋子,则打印 No.

否则,按以下格式打印此类展示位置:

Yes
p_1 r_1 c_1
\vdots
p_{R+B} r_{R+B} c_{R+B}

在这里, p_i is R 如果 i放置的第块是红色的,并且 B 如果是蓝色的。 r_i 和 c_i 是介于 1 和 10^9 (含),表明 i- 第一块被放置在正方形上 (r_i,c_i).


示例输入 1

3
2 3
1 1
4 0

示例输出 1

Yes
B 2 3
R 3 2 
B 2 2
B 3 3
R 2 4
No
Yes
R 1 1
R 1 2
R 2 2
R 2 1

对于第一个测试用例,如果我们提取左上角 4\times 5 棋盘的方格,棋子的位置如下:

.....
.BBR.
.RB..
.....

在这里, R 表示该方块上有一个红色棋子, B 表示该方块上有一个蓝色棋子,并且 . 表示空方块。

对于第二个测试用例,没有放置满足条件的棋子。