a268: 河內塔問題
標籤 :
通過比率 : 81% (43 人 / 53 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2012-09-22 11:47

內容

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

        我們的問題比較複雜一點,給定圓盤的初始狀態以及目標狀態,問至少要移動幾次能從初始狀態到目標狀態。
輸入說明
        每個測資檔包含多筆測資。每筆測資包含三行,第一行是一個正整數N (1<=N<=10000),代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有N個正整數,第i個數Si代表第i小的圓盤是套在Si上,其中Si只可能是123。當N=0時代表輸入結束。
輸出說明
        對每筆測資輸出一行,代表從初始狀態到目標狀態至少要移動幾次圓盤。由於答案可能很大,請輸出mod 1,000,000,007的結果。
範例輸入
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
範例輸出
6
7
3
0
147483633
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 :
標籤:
出處:
2011成功高中校內賽複賽第四題 [編輯:
david942j (文旋)
]


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