1158 - 神父过河
Time Limit : 1 秒
Memory Limit : 128 MB
n 个神父和 n 个恶魔一同来到了河岸,他们现在要过河。
他们可以通过一个容量为 m 的船过去。
在渡河过程中,在河岸和船上,神父的数量都不能小于恶魔的数量,否则会被吃掉。
船不会自己划,因此最少需要一个神父或者一个恶魔去划船。
请你设计一个渡河流程,使得 n 个神父和 n 个恶魔都能过河。
Input
第一行两个整数 n 和 m,含义如题目描述。
Output
第一行输出最少的步数 t,如果不行,输出 -1.
接下来 t 行,每行表示哪些去划船。如果有多少方案,由于河流湍急,输出乘船数交多的。
如果还有多少种方案,输出神父较多的。可以认为,如果有多种方案,输出字典序最大的。
字典序的比较流程:
(1)数量多的优先
(2)神父的数量多的优先
具体输出方式,见样例。
Examples
Input
3 2
Output
11 1 father and 1 devil. 1 father. 2 devils. 1 devil. 2 fathers. 1 father and 1 devil. 2 fathers. 1 devil. 2 devils. 1 father. 1 father and 1 devil.
Hint
注意单复数。
对于 30\% 的数据共 6 组,n 从 3 到 8 且 n=m;
对于 70\% 的数据,n 的范围 [2,50];
对于 100\% 的数据,n 的范围 [2,100],m≤n;