1355 . 河內之塔-蘿莉塔
TopCoder
Tags
Description
傳說在古老的印度，有一座神廟，據說它是宇宙的中心。
在廟宇中放置了一塊上面插有三根長木釘的木板，在其中的一根木釘上，從上至下被放置了 64 片直徑由小至大的圓環形金屬片。
古印度教的天神指示祂的僧侶們將 64 片的金屬片移至三根木釘中的其中一根上。
規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的金屬片都是直徑較小的被放在上層。
直到有一天，僧侶們能將 64 片的金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。
僧侶極希望能早點結束這繁重的工作，於是來求助於你，要如何才能有效率的進行這工作呢？
Input Format
輸入只含有一個數字 $n (1 \le n \le 10)$ 代表金屬片的數量
Output Format
請輸出當有 $n$ 片金屬片的時候要按照怎樣的步驟可以最快從 1 號柱子搬到 3 號柱子（格式請參照範例輸出）
Sample Input 1
3
Sample Output 1
#1 : move the dish from #1 to #3
#2 : move the dish from #1 to #2
#3 : move the dish from #3 to #2
#4 : move the dish from #1 to #3
#5 : move the dish from #2 to #1
#6 : move the dish from #2 to #3
#7 : move the dish from #1 to #3
#2 : move the dish from #1 to #2
#3 : move the dish from #3 to #2
#4 : move the dish from #1 to #3
#5 : move the dish from #2 to #1
#6 : move the dish from #2 to #3
#7 : move the dish from #1 to #3
Hints
Problem Source
原TIOJ1355 / 快樂暑假營第一次練習比賽。Problem Setter：hallogameboy
2024/07/13 Update: Reformatted & added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |