阿麥在假日市集裡擺了一個攤子賣煎餅。
考量每個人的食量不同,他決定販售 種不同大小的煎餅,依照小到大由 編號到 ,並預計將同一種大小的煎餅堆成一疊方便選購。
每疊煎餅至多只能疊 片,否則會因為過高而倒塌。
阿麥每煎好一片就將該片煎餅放到攤位檯面上,但因為太過匆忙,不同大小的煎餅被堆放在同一疊。
當他注意到時,攤位上已有 疊煎餅,每疊都恰有 片,而每種大小的煎餅也恰有 片。
阿麥想利用煎餅鏟來移動這些煎餅,調整回他預期的擺設。
他只能透過下面的動作來調整煎餅位置:
- 將煎餅鏟插入某疊煎餅中的某兩片之間
- 將煎餅鏟上方所有的煎餅放置至另一疊的上方 (鏟子上方的煎餅順序不變)
因攤位檯面大小有限,除了既有的 疊煎餅外,剩餘的空間僅能再容納一疊煎餅;
此外,調整過程不可有任一疊超過 片,否則該疊煎餅就會倒塌。
請協助阿麥將同樣大小的煎餅調整為同一疊,並且讓較小的煎餅排在較左邊。
舉例來說,若 ,,一開始的 疊煎餅如下圖 (最右邊為檯面剩餘空間):
:::align{center}
:::
一個可能的調整方式如下,將煎餅鏟插入最左邊的下面兩片之間,並移動至右方的剩餘空間:
:::align{center}
:::
將煎餅鏟插入中間的下面兩片之間,並移動至最左邊:
:::align{center}
:::
將最左邊最上面的煎餅鏟至中間:
:::align{center}
:::
接著再將最右邊的兩個煎餅分別鏟到第 , 疊,便完成了阿麥預期的擺設方式:
:::align{center}
:::
請寫一個程式幫助阿麥將各種大小的煎餅移動到想要的位置,
由於移動方法很多可以輸出任何一種可行的移動方法,
但移動的次數需要在 次以內。