2011年9月24日 星期六

11925 - Generating Permutations



由 1, 2, 3, ..., n 的序列開始,經過一些步驟重新排列後,可以得到另一組序列。給定一組目標序列,請你由1, 2, 3, ..., n的序列開始,經由下列兩種操作來得到目標序列:
  • 操作 1:對最前面兩個數做交換,例如:3, 2, 4, 5, 1變為2, 3, 4, 5, 1。
  • 操作 2:將最前面的數移到最後面,例如由3, 2, 4, 5, 1變為2, 4, 5, 1, 3。

Input

輸入有多組測試資料,每組資料一列,其第一個整數為 n,n值介於1到300之間,接下來共有n個整數表示目標序列。當 n = 0 表示資料結束。

Output

請對每組測試資料輸出一列,表示使原序列(1, 2, 3, ..., n)轉換為目標序列的操作步驟依序為何,請輸出'1'表示執行操作1,輸出'2'表示執行操作2。
輸出的步驟總數並不要求要最小化,但不能超過2n*n次。若不需任何步驟即可產生目標序列,請輸出一列空行。

Sample Input 

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

Sample Output 

1
2
12122


原文出處

沒有留言:

張貼留言