[UVa] 10254 - The Priest Mathematician

題目網址: http://goo.gl/v9zQ2y

題意:
(from luckycat)


解 法:
假設 f(n) 是以 4 根木棒的解法，求解 f(n) ，先把 k 塊圓板移到第四根木棒上，接著以 3 根木棒的方法移動 n-k 塊圓板至目標木棒，接著再以 4 根木棒的解法移動 k 塊圓板至目標木棒，由於以 3 根木棒的方法移動 k 個圓板會等於 (2^k)-1，所以 f(n) = min{ 2*f(k) + 2^(n-k) -1, 1 <= k < n }，先嘗試跑前幾個答案。

 f[0] = 0
f[1] = 1 = f[0] + 2^0
f[2] = 3 = f[1] + 2^1
f[3] = 5 = f[2] + 2^1
f[4] = 9 = f[3] + 2^2
f[5] = 13 = f[4] + 2^2
f[6] = 17 = f[5] + 2^2
f[7] = 25 = f[6] + 2^3
f[8] = 33 = f[7] + 2^3
f[9] = 41 = f[8] + 2^3
f[10] = 49 = f[9] + 2^3
f[11] = 65
f[12] = 81
f[13] = 97
f[14] = 113
f[15] = 129
f[16] = 161
f[17] = 193
f[18] = 225
f[19] = 257
f[20] = 289

會發現規律 f[i] = f[i-1] + 2^k, i > 0 & k 是第一個滿足 (k*(k+1))/2 >= i 的值。
由於 141*142/2 >= 10000 ，k 會到達 141，所以需要用大數。

TAG: Math, BigNum,

注意:

程式碼: