ProjectEuler 406 Guessing Game - 拼圖

406. Guessing Game

http://projecteuler.net/problem=406


我們要試著藉由問問題來找出一個包含在 { 1 , 2 , 3 , ... , n } 中的隱藏的正整數，

每當我們問一個數字（問題），我們可能會得到三種不同的結果：

‧你猜的數字比隱藏數字還要低（花費 a 點），或

‧你猜的數字比隱藏數字還要高（花費 b 點），或

‧完全正確！（遊戲就結束了）


給定 n, a, b 的值，最佳策略將會把最糟情況的花費降低。


舉個例子，如果 n = 5, a = 2, b = 3, 我們第一次猜測為 2

如果我們被告知 2 高於隱藏數字（花費 3 點），我們便會知道隱藏數字為 1。

如果我們被告知 2 低於隱藏數字（花費 2 點），下一次猜測我們就猜 4。

如果我們被告知 4 高於隱藏數字（花費 3 點），我們便會知道隱藏數字為 3，並花費了

2 + 3 = 5 點。

如果我們被告知 4 低於隱藏數字（花費 2 點），我們便會知道隱藏數字為 5，並花費了

2 + 2 = 4 點。

因此用這招，最糟的情況就是花費 5 點，我們可以發現這是最糟情況中花費最低的策略。


使 C(n,a,b) 為使用最佳策略中最糟情況的花費值，當給定 n, a, b。


這兒有幾個例子：

C(5, 2, 3) = 5

C(500, √2, √3) = 13.22073197 ...

C(20000, 5, 7) = 82

C(2000000, √5, √7) = 49.63755955 ...


使 F_k 為費氏數列：F_k = F_(k-1) + F_(k-2) 當 F_1 = F_2 = 1。


求Σ_1≦k≦30 C(10^12, √k, √F_k) , 給出答案到小數點後 8 位。

--