d882: 10254 - The Priest Mathematician
Tags : DP 大數 河內塔
Accepted rate : 67人/82人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-28 14:11

Content

E. Lucas 在 1883 年創造的"Towers of Hanoi"難題背後的古老民間傳說是很有名的。一個最近的傳說告訴我們在 Benares 的 Brahmin 和尚們絕不相信,在他們把 64 片盤子從一個柱子全部搬到另外一個的那一刻,世界就會毀滅,所以他們決定要儘快完成這個工作。

圖片:四根柱子的 Tower of Hanoi

一個在 Benares 神殿的的祭司(他喜歡數學)跟他的同事保證,如果用一個額外的柱子,就可以在下午完成搬運(他們認為每秒可以搬一個盤子)。他們不相信他,但是他向他們提出以下策略:

-- 把最上面的 k 個盤子搬到備用的柱子。
-- 然後用原本的三個柱子的策略去把剩下的 n-k 的盤子搬到他們的目標。
-- 最後用四個柱子把最上面的 k 個盤子搬到目標。

他計算 k 的值使得移動的次數最少,結果是總共 18433 次,所以他們只要花 5 個小時 713 秒,比不用一個額外柱子的 5000 億年(他們要搬 2^64-1 次盤子,你相信嗎?)好多了。

試著照這個聰明的祭司的策略計算用四個柱子要搬幾次。根據 Brahma 固定不變的法律,一次只能移動一個盤子,而且不能放在比較小的盤子上面。當然,主要的目標是計算 使搬移次數(就算不確定這是不是最佳的移動次數)最少的 k

Input

輸入檔包含很多行輸入,每行都有一個整數 N,表示要搬的盤子數量。這裡 0<=N<=10000。Input 以 end-of-file 結束。

Output

對每行輸入輸出一行把 N 個盤子搬到最後的柱子需要搬動幾次。

Sample Input #1
1
2
28
64
Sample Output #1
1
3
769
18433
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
DP 大數 河內塔
出處:
UVa10254 [管理者:
david942j (文旋)
]


ID User Problem Subject Hit Post Date
14992
k034006 (Sine Wu)
d882
略解
615 2018-08-28 23:38