← 返回题目列表

Codeforces · 737/F

F. 盘子脏了

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

一次庆祝活动结束后,尼基塔的厨房里有一堆脏盘子。尼基塔必须将它们清洗并放入烘干机中。在干燥机中,盘子也应堆叠放置,并且盘子尺寸应从下到上增加。所有盘子的尺寸都是不同的。

Nikita 没有那么多可用空间,具体来说,他只能再容纳一叠盘子。因此,他只能进行这样两个操作:

- 从脏堆顶部取出 1 到 a 任意数量的盘子,清洗它们并将它们放入中间堆。
- 从中​​间堆顶部取出 1 到 b 任意数量的盘子,并将它们放入烘干机中的堆中。

请注意,执行每项操作后,板的放置顺序与操作前相同。

给定了脏堆栈中按从下到上的顺序排列的盘子 s1、s2、...、sn 的大小,以及整数 a 和 b。所有尺寸都是不同的。编写一个程序来确定 Nikita 是否可以将盘子按照从上到下递增的顺序放入烘干机中。如果他能够做到这一点,程序应该找到一些操作序列(不一定是最佳的)来实现它。

输入

第一行包含三个整数 n、a 和 b (1 ≤ n ≤ 2000, 1 ≤ a, b ≤ n)。第二行包含整数 s1、s2、...、sn (1 ≤ si ≤ n) — 按从下到上的顺序排列的板的尺寸。所有尺寸都是不同的。

输出

如果有解决方案,请在第一行打印“YES”。在本例中,在第二行中打印整数 k — 操作次数。然后在 k 行中打印操作,每行一个。每个操作由两个整数 tj 和 cj 描述,其中 tj = 1,如果操作是从脏堆叠中清洗顶部 cj 位置并将它们放入中间堆叠上,并且 tj = 2,如果操作是将顶部 cj 板从中间堆叠移动到干燥机。

如果没有解决方案,请打印单行“NO”。

如果有多个解决方案,请打印其中任何一个。请注意,没有必要最小化操作数量。

示例

输入 #1

6 2 3
2 3 6 4 1 5

输出 #1

YES
8
1 2
1 1
2 1
1 2
1 1
2 1
2 1
2 3

输入 #2

7 7 7
1 2 3 4 5 6 7

输出 #2

YES
2
1 7
2 7

输入 #3

7 1 1
1 2 3 4 5 6 7

输出 #3

YES
14
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1

输入#4

4 2 2
3 2 1 4

输出#4

NO

注意

在第一个示例中,板的初始顺序是 2, 3, 6, 4, 1, 5。以下是每次操作后堆栈的样子:

- [1 2]:脏堆栈:6、 4、 1、 5。中间堆栈:2、 3。烘干机已空。
- [1 1]:脏堆栈:4、 1、 5。中间堆栈:6、 2、 3。烘干机已空。
- [2 1]:脏烟囱:4、 1、 5。中间烟囱:2、 3。干燥烟囱:6。
- [1 2]:脏烟囱:5。中间烟囱:4、 1、 2、 3。烘干机烟囱:6。
- [1 1]:没有脏盘子。中间烟囱:5、 4、 1、 2、 3。烘干机烟囱:6。
- [2 1]:没有脏盘子。中间烟囱:4、 1、 2、 3。干燥烟囱:5、 6。
- [2 1]:没有脏盘子。中间烟囱:1、 2、 3。干燥烟囱:4、 5、 6。
- [2 3]:所有板都在干燥器中:1、 2、 3、 4、 5、 6。

这在第三个示例中是不可能的,因为不允许同时移动多个板。可以一张一张地清洗印版,以便将它们以相反的顺序放置到中间堆上,然后将印版一张一张地移至干燥机。最后的顺序是正确的。