9040:火车车厢重排

Time/Memory Limit:1000 MS/32768 K
Submitted: 508 Accepted: 350

 Problem Description

一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n,即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢,车厢的编号应与车站的编号相同。这样,在每个车站只需卸掉最后一节车厢。因此,对于给定的任意次序车厢,必须进行重新排列,使其符合要求。车厢重排工作可通过转轨站完成,在转轨站中有一个入轨、一个出轨和k个缓冲轨,缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式工作,现要求设计算法解决火车车厢重排问题。

 Input

有多组数据,每组第一行为车厢节数n和缓冲轨数目k(2<=k<=5,k<=n<=10),第二行为初始给定的车厢编号次序序列。

 Output

若给定的车厢编号次序序列可重排,则输出1;否则输出0。

 Sample Input

9 3
3 6 9 2 4 7 1 8 5
9 3
3 6 9 2 4 7 5 8 1

 Sample Output

1
0

 Hints

参见主教材P73

 Author

hwt

 Recommend

zh