Dirty plates

题意翻译

题目描述 你有三个栈$s1,s2,s3$，其中栈$s1$中有$N$个数。现在你有两种操作： 1、将$s1$中栈顶的$c$个元素压入$s2$中，在$s2$中的顺序与在$s1$中的顺序相同，需要满足$1 \leq c \leq a$。 2、将$s2$中栈顶的$c$个元素压入$s3$中，在$s3$中的顺序与在$s2$中的顺序相同，需要满足$1 \leq c \leq b$。 现在，给定$N,a,b$与$s1$中元素的初始顺序，问是否存在一种方案，使得使用上面两种操作之后，所有元素都在$s3$中且$s3$从栈底到栈顶为一个单调递减的序列。你给出的方案不一定要是最优的。 输入格式 第一行三个正整数$N,a,b(1 \leq N \leq 2000 , 1 \leq a , b \leq N)$，意义如题目所述 接下来一行$N$个正整数$s_i$，从栈顶到栈底描述栈中一个元素的值。保证序列$\{s_i\}$为一个长度为$N$的排列。 输出格式 如果存在一种方案，第一行输出$Yes$，接下来一行一个正整数$K$表示你给出的方案中的操作次数，接下来$K$行每行两个整数$t,c$，若$t=1$，表示将$s1$中栈顶的$c$个元素压入$s2$中,若$t=2$表示将$s2$中栈顶的$c$个元素压入$s3$中。如果没有方案满足条件，只需输出一行$No$。

题目描述

After one of celebrations there is a stack of dirty plates in Nikita's kitchen. Nikita has to wash them and put into a dryer. In dryer, the plates should be also placed in a stack also, and the plates sizes should increase down up. The sizes of all plates are distinct. Nikita has no so much free space, specifically, he has a place for only one more stack of plates. Therefore, he can perform only such two operations: - Take any number of plates from $ 1 $ to $ a $ from the top of the dirty stack, wash them and put them to the intermediate stack. - Take any number of plates from $ 1 $ to $ b $ from the top of the intermediate stack and put them to the stack in the dryer. Note that after performing each of the operations, the plates are put in the same order as they were before the operation. You are given the sizes of the plates $ s_{1},s_{2},...,s_{n} $ in the down up order in the dirty stack, and integers $ a $ and $ b $ . All the sizes are distinct. Write a program that determines whether or not Nikita can put the plates in increasing down up order in the dryer. If he is able to do so, the program should find some sequence of operations (not necessary optimal) to achieve it.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ a $ and $ b $ ( $ 1<=n<=2000 $ , $ 1<=a,b<=n $ ). The second line contains integers $ s_{1},s_{2},...,s_{n} $ ( $ 1<=s_{i}<=n $ ) — the sizes of the plates in down up order. All the sizes are distinct.

输出格式

In the first line print "YES" if there is a solution. In this case, in the second line print integer $ k $ — the number of operations. Then in $ k $ lines print the operations, one per line. Each operation is described by two integers $ t_{j} $ and $ c_{j} $ , where $ t_{j}=1 $ , if the operation is to wash the top $ c_{j} $ places from the dirty stack and put them onto the intermediate stack, and $ t_{j}=2 $ , if the operation is to move th top $ c_{j} $ plates from the intermediate stack to the dryer. In case there is no solution, print single line "NO". If there are multiple solutions, print any of them. Note that it is not necessary to minimize the number of operations.

输入输出样例

输入样例 #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

说明

In the first example the initial order of plates was $ 2,3,6,4,1,5 $ . Here is how the stacks look like after each of the operations: - \[1 2\]: Dirty stack: $ 6,4,1,5 $ . Intermediary stack: $ 2,3 $ . The dryer is empty. - \[1 1\]: Dirty stack: $ 4,1,5 $ . Intermediary stack: $ 6,2,3 $ . The dryer is empty. - \[2 1\]: Dirty stack: $ 4,1,5 $ . Intermediary stack: $ 2,3 $ . Dryer stack: $ 6 $ . - \[1 2\]: Dirty stack: $ 5 $ . Intermediary stack: $ 4,1,2,3 $ . Dryer stack: $ 6 $ . - \[1 1\]: There are no dirty plates. Intermediary stack: $ 5,4,1,2,3 $ . Dryer stack: $ 6 $ . - \[2 1\]: There are no dirty plates. Intermediary stack: $ 4,1,2,3 $ . Dryer stack: $ 5,6 $ . - \[2 1\]: There are no dirty plates. Intermediary stack: $ 1,2,3 $ . Dryer stack: $ 4,5,6 $ . - \[2 3\]: All the plates are in the dryer: $ 1,2,3,4,5,6 $ . In the second example it is possible to wash all the plates in one operation, and then move them all to the dryer.This is not possible in the third example, because it is not permitted to move more than one plate at the same time. It is possible to wash plates one by one so that they are placed onto the intermediary stack in the reverse order, and then move plates one by one to the dryer. The final order is correct.