TopCoder

User's AC Ratio

87.7% (57/65)

Submission's AC Ratio

56.9% (62/109)

Description

傳說在古老的印度,有一座神廟,據說它是宇宙的中心。

在廟宇中放置了一塊上面插有三根長木釘的木板,在其中的一根木釘上,從上至下被放置了64片直徑由小至大的圓環形金屬片。

古印度教的天神指示祂的僧侶們將64片的金屬片移至三根木釘中的其中一根上。

規定在每次的移動中,只能搬移一片金屬片,並且在過程中必須保持金屬片由上至下是直徑由小至大的次序,也就是說不論在那一根木釘上,圓環形的金屬片都是直徑較小的被放在上層。

直到有一天,僧侶們能將64片的金屬片依規則從指定的木釘上全部移動至另一根木釘上,那麼,世界末日即隨之來到,世間的一切終將被毀滅,萬物都將至極樂世界。

僧侶極希望能早點結束這繁重的工作,於是來求助於你,要如何才能有效率的進行這工作呢?

Input Format

輸入只含有一個數字n(1<=n<=10)代表金屬片的數量

Output Format

請輸出當有n片金屬片的時候要按照怎樣的步驟可以最快從1號柱子搬到3號柱子(格式請參照範例輸出)

Sample Input

3

Sample Output

#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

Hints

Problem Source

原TIOJ1355 / 快樂暑假營第一次練習比賽。Problem Setter:hallogameboy

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536