猜数游戏

集合$\{1,2,\ldots,n\}$中有一个隐藏数X，我们需要通过一系列问题来确定该数。

每次提问时我们报出一个数，并会得到如下三种问答之一：

X大于该数，此时我们需要支付a元。

X小于该数，此时我们需要支付b元。

X大于该数，游戏结束。

给定n,a,b的值，所谓最优策略，是指能使最坏情况下总成本最小的策略。

例如，若$n=5, a=2, b=3$，则第一次应该猜2。

若$2=X$，则游戏直接结束，总成本为0元。

若$2>X$，则支付$b=3$元，此时可以知道$X=1$，总成本为3元。

若$2 < X$，则支付$a=2$元，并继续猜4。

若$4=X$，则游戏结束，总成本为$2$元。

否则若$4>X$，则可知$X=3$，此时需要再支付$b=3$元，因此总成本为$2+3=5$元。

若$4 < X$，则可知$X=5$，此时需要再支付$a=2$元，因此总成本为$2+2=4$元。

因而此策略在最坏情况下的总成本是5元。可以证明这也是最坏情况总成本的最小值，因此这就是一个最优策略。

记$C(n, a, b)$是$n, a, b$所对应的最优策略在最坏情况下的总成本，可以验证： \begin{align*} C(5, 2, 3)&=5 \\ C(500, \sqrt 2, \sqrt 3)&=13.22073197\ldots \\ C(20000, 5, 7)&=82 \\ C(2000000, \sqrt 5, \sqrt 7)&=49.63755955\ldots \end{align*} 记$F_k$是以$F_1=F_2=1$为初值的斐波那契数列，求$\sum_{k=1}^{30}C(10^{12}, \sqrt k, \sqrt{F_k})$，结果四舍五入到小数点后八位。

本题难度:

解答

本题需要逆向思考，考虑恰好支付i次a和j次b的情况下能够猜出哪些数，再通过增加x和y拓展可以猜出的数的范围，直到超过n，此时ai+bj就是最小成本。

最终结果是$36813.12757207$。

注：为便于格式化输出，以下代码为Python 3。

import bisect,math

target=10**12
epsilon=10**(-10)

def C(a,b):
    if a>b:
        a,b=b,a
    x=[0]
    i=j=0
    d=[1]
    while True:
        pv=x[-1]
        while x[i]+a<=pv+epsilon:
            i+=1
        while x[j]+b<=pv+epsilon:
            j+=1
        v=min(x[i]+a,x[j]+b)
        x.append(v)
        s=1
        if v>=a:
            s+=d[bisect.bisect(x,v-a+epsilon)-1]
        if v>=b:
            s+=d[bisect.bisect(x,v-b+epsilon)-1]
        if s>=target:
            return v
        d.append(s)

f=[0,1]
for i in range(30):
    f.append(f[-1]+f[-2])

print(f"{sum(C(math.sqrt(k),math.sqrt(f[k])) for k in range(1,31)):.8f}")