← 返回题目列表

Codeforces · 2232/D

D. 神奇的分层蛋糕

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

爱丽丝完成了一个神奇的分层蛋糕,有$$$n$$$个神奇层,其中每一层都小于其下面的所有层(即第一层是最小的,第$$$n$$$层是最大的)。现在,她需要您的帮助将其从厨房运送到派对现场。由于不可能一次性搬运整个蛋糕,所以她还为你准备了一个仓库,以方便运输过程。

由于蛋糕是神奇的,当且仅当其上方正好有 $$$a_i$$$ 层蛋糕时,第 $$$i$$$ 层蛋糕才可移动。

在每个动作中,您可以选择 正好一个 从任何位置移动蛋糕层,并将其移动到任何其他位置的分层蛋糕顶部。然而,为了保留蛋糕的结构,如果目的地有分层蛋糕,则移动的层必须位于严格大于它的层上。例如,您无法将大小为 $$$4$$$ 的图层移动到已存在大小为 $$$3$$$ 的图层的位置之上。

聚会即将开始,所以我们需要快速行动。帮助爱丽丝在 $$$2^n$$$ 步内将蛋糕运送到派对上,否则报告这是不可能的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 20$$$) – 神奇分层蛋糕的层数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq n$$$),表示蛋糕需要在第 $$$i$$$ 层之上有多少层才能移动。

保证所有测试用例的$$$2^n$$$总和不超过$$$2^{20}$$$。

输出

对于每个测试用例,如果无法将神奇的分层蛋糕移动到聚会地点,则输出 NO.

否则,在第一行输出 是.

然后,在下一行输出一个整数 $$$k$$$ ($$$0 \leq k \leq 2^n$$$) – 运输蛋糕的移动次数。

对于以下 $$$k$$$ 行,输出整数 $$$\mathrm{id}$$$、$$$\mathrm{from}$$$、$$$\mathrm{to}$$$ ($$$1 \le \mathrm{id} \le n, 1 \le \mathrm{from}, \mathrm{to} \le 3$$$):蛋糕层你想要移动,它的当前位置和目的地,其中 $$$1$$$ 代表爱丽丝的厨房,$$$2$$$ 代表爱丽丝的仓库,$$$3$$$ 代表聚会地点。

示例

输入
复制

3
3
0 0 0
3
0 1 2
3
2 2 2

输出
复制

YES
7
1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3
YES
3
3 1 3
2 1 3
1 1 3
NO

注意

测试用例 $$$1$$$ 和 $$$2$$$ 解决方案的可视化如下 gif 所示:

在第三个测试用例中,可以证明不可能将蛋糕的所有层移动到派对站点。