a268. 河內塔問題 - 高中生程式解題系統

內容

相信大家都知道著名的河內塔問題。簡單來說，就是有三根柱子，柱子上可以套多個圓盤，圓盤大小都不同，但是每次移動一個圓盤的時候都不能有較大的圓盤在較小的圓盤上。一般來說一開始的初始狀態是所有圓盤都在同一根柱子上，目標是在不違反規則的條件下，至少移動幾次圓盤可使所有圓盤移動到另外一根柱子上。

我們的問題比較複雜一點，給定圓盤的初始狀態以及目標狀態，問至少要移動幾次能從初始狀態到目標狀態。

輸入說明

每個測資檔包含多筆測資。每筆測資包含三行，第一行是一個正整數N (1<=N<=10000)，代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有N個正整數，第i個數S_i代表第i小的圓盤是套在S_i上，其中S_i只可能是1或2或3。當N=0時代表輸入結束。

輸出說明

對每筆測資輸出一行，代表從初始狀態到目標狀態至少要移動幾次圓盤。由於答案可能很大，請輸出mod 1,000,000,007的結果。

範例輸入 #1

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

範例輸出 #1

測資資訊：

記憶體限制： 512 MB

提示：

標籤:

出處:

2011 成功高中校內賽複賽第四題 [管理者： david942j (文旋) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」