Project Euler 406

发表于 2026-01-13 分类于 Project Euler 阅读次数：本文字数： 3.8k 阅读时长 ≈ 3 分钟

Project Euler 406

题目

Guessing Game

We are trying to find a hidden number selected from the set of integers \(\{1, 2, \dots, n\}\) by asking questions. Each number (question) we ask, we get one of three possible answers:

“Your guess is lower than the hidden number” (and you incur a cost of \(a\)), or
“Your guess is higher than the hidden number” (and you incur a cost of \(b\)), or
“Yes, that’s it!” (and the game ends).

Given the value of \(n, a\), and \(b\), an optimal strategy minimizes the total cost for the worst possible case.

For example, if \(n = 5, a = 2\), and \(b = 3\), then we may begin by asking “\(\mathbf{2}\)” as our first question.

If we are told that \(2\) is higher than the hidden number (for a cost of \(b=3\)), then we are sure that “\(\mathbf{1}\)” is the hidden number (for a total cost of \(\color{blue}{\mathbf{3}}\)).

If we are told that \(2\) is lower than the hidden number (for a cost of \(a=2\)), then our next question will be “\(\mathbf{4}\)”.

If we are told that \(4\) is higher than the hidden number (for a cost of \(b=3\)), then we are sure that “\(\mathbf{3}\)” is the hidden number (for a total cost of \(2+3=\color{blue}{\mathbf{5}}\)).

If we are told that \(4\) is lower than the hidden number (for a cost of \(a=2\)), then we are sure that “\(\mathbf{5}\)” is the hidden number (for a total cost of \(2+2=\color{blue}{\mathbf{4}}\)).

Thus, the worst-case cost achieved by this strategy is \(\color{red}{\mathbf{5}}\) It can also be shown that this is the lowest worst-case cost that can be achieved.

So, in fact, we have just described an optimal strategy for the given values of \(n, a,\) and \(b\).

Let \(C(n, a, b)\) be the worst-case cost achieved by an optimal strategy for the given values of \(n, a\) and \(b\).

Here are a few examples:

\(\begin{aligned} &C(5, 2, 3) = 5\\ &C(500, \sqrt 2, \sqrt 3) = 13.22073197\dots\\ &C(20000, 5, 7) = 82\\ &C(2000000, \sqrt 5, \sqrt 7) = 49.63755955\dots\\ \end{aligned}\)

Let \(F_k\) be the Fibonacci numbers: \(F_k=F_{k-1}+F_{k-2}\) with base cases \(F_1=F_2= 1\).

Find \(\displaystyle \sum \limits_{k = 1}^{30} {C \left (10^{12}, \sqrt{k}, \sqrt{F_k} \right )}\), and give your answer rounded to \(8\) decimal places behind the decimal point.

解决方案

可见，任意策略都对应一棵二叉搜索树：

每个节点标一个“猜测值”；
若回答 “higher”（说明猜大了），进入左子区间，路径代价增加 \(b\)；
若回答 “lower”（说明猜小了），进入右子区间，路径代价增加 \(a\)；
若猜中，则停在该节点（不增加代价）。

因此，一条从根到某节点的路径，若其中出现了 \(i\) 次 “lower”、\(j\) 次 “higher”，那么该路径累计代价为\(ia+jb.\)

最坏情况下的总代价，就是整棵树中代价最大的那条“错误反馈序列”对应的代价。

我们反过来，与其直接求 \(C(n,a,b)\)，不如先考虑在最坏总代价不超过 \(T\) 的前提下，最多能保证猜中多少个候选数？

设这个最大可覆盖规模为 \(G(T)\)。如果我们能计算 \(G(T)\)，那么\(C(n,a,b)=\min\{T\mid G(T)\ge n\}.\)

考虑预算为 \(T\) 的最优策略在根节点的第一次猜测。无论根节点猜哪个数，它都会把区间分成两段：

若收到 “lower”，付出 \(a\)，剩余预算 \(T-a\)，进入右侧子问题；
若收到 “higher”，付出 \(b\)，剩余预算 \(T-b\)，进入左侧子问题；
若猜中，直接结束（这对应“根节点本身”也能代表一个可覆盖的隐藏数）。

因此，在预算 \(T\) 下最多能覆盖的数量满足\(G(T)=1+G(T-a)+G(T-b),\)并约定当预算为负时无法再继续分支：\(G(T)=0 (T<0).\)

这条递推的直观意义是：根节点贡献 \(1\) 个可能值；其余分别由两边子树在预算 \(T-a\) 与 \(T-b\) 下的最优覆盖数贡献。

注意到 \(G(T)\) 只会在某些关键点发生变化：当 \(T\) 穿过某个形如\(ia+jb (i,j\in\mathbb{Z}_{\ge 0})\)的值时，递推中 \(T-a\) 或 \(T-b\) 才可能“跨过”新的关键点，导致 \(G(T)\) 增加。

于是我们把所有可表示的代价\(\mathcal{C}=\{ia+jb\mid i,j\ge 0\}\)，按从小到大排序，得到一个递增序列\(0=c_0<c_1<c_2<\cdots\)并只在这些 \(c_t\) 上计算 \(G(c_t)\)。一旦找到最小的 \(c_t\) 使得 \(G(c_t)\ge n\)，它就是答案 \(C(n,a,b)\)。

直接枚举所有 \(i,j\) 会很慢，但这里有一个重要结构：集合 \(\mathcal{C}\) 在加 \(a\) 与加 \(b\) 下闭合。

也就是说，若某个代价已经出现为 \(c_t\)，那么 \(c_t+a\) 与 \(c_t+b\) 也是未来会出现的候选代价。并且随着 \(t\) 增大，序列 \({c_t+a}\) 与 \({c_t+b}\) 都是递增的。

因此，下一个台阶代价一定是两条递增序列的“归并最小值”：\(c'=\min(c_{p_a}+a,\ c_{p_b}+b),\)其中 \(p_a,p_b\) 是两个指针，分别指向“下一次从哪一个旧台阶加 \(a\) / 加 \(b\) 生成新台阶”。

令状态 \((c_t,F_t)\) 表示：

\(c_t\)：第 \(t\) 个（从 \(0\) 开始）出现的“关键代价台阶”；
\(F_t\)：在最坏总代价不超过 \(c_t\) 时，能够覆盖的最大候选数规模（也就是 \(G(c_t)\) 的值）。

初始化显然是：\(c_0=0, F_0=1,\)因为代价为 \(0\) 时只能一次猜中一个数。

设当前两个指针为 \(p_a,p_b\)，则候选的新台阶代价为：\(c'=\min(c_{p_a}+a,\ c_{p_b}+b)\)

当我们决定这个新台阶 \(c'\) 出现时，它对应的覆盖能力满足（由 \(G(T)=1+G(T-a)+G(T-b)\) 推得）：\(F' = F_{p_a}+F_{p_b}.\)

直观理解：新台阶出现时，允许的“错误反馈序列集合”相当于把“还能再走一次 \(a\)”与“还能再走一次 \(b\)”这两部分组合起来；对应覆盖规模相加（这是该题最关键的可压缩性质）。

指针更新规则就是归并两条序列：

若 \(c_{p_a}+a<c_{p_b}+b\)，则新台阶来自 \(p_a\) 方向，令 \(p_a\leftarrow p_a+1\)；
若 \(c_{p_a}+a>c_{p_b}+b\)，则令 \(p_b\leftarrow p_b+1\)；
若二者相等（例如 \(a=b\) 或更一般的有理比值造成碰撞），则同时前进：\(p_a\leftarrow p_a+1, p_b\leftarrow p_b+1.\)

不断生成新台阶，直到出现某一步满足\(F_t>n,\)那么答案就是前一个台阶代价：\(C(n,a,b)=c_{t-1}.\)

代码

N = 10**12
M = 30

def C_opt(n: int, a: float, b: float) -> float:
    """
    返回 C(n, a, b)：最坏情况下的最小总代价。
    使用“台阶归并 DP”（两指针）：
      (vn[t], vc[t]) 依次生成，直到 vn_new > n，则答案为 vc[-2]。
    """
    if a > b:
        a, b = b, a

    # vn: 对应覆盖规模的台阶序列（单调增）
    # vc: 对应代价台阶序列（单调增）
    vn = [1]
    vc = [0.0]

    pa = 0
    pb = 0

    # 数值误差容忍（只用于判断“是否相等”）
    eps = 1e-12

    while True:
        ca = vc[pa] + a
        cb = vc[pb] + b

        nn = vn[pa] + vn[pb]
        cc = ca if ca < cb else cb

        vn.append(nn)
        vc.append(cc)

        # 归并指针更新
        if abs(ca - cb) <= eps * (1.0 + abs(cc)):
            pa += 1
            pb += 1
        elif ca < cb:
            pa += 1
        else:
            pb += 1

        # 按台阶判定：第一次超过 n 时，答案在前一格
        if nn > n:
            return vc[-2]


def fib_list(m: int):
    F = [0] * (m + 1)
    F[1] = F[2] = 1
    for i in range(3, m + 1):
        F[i] = F[i - 1] + F[i - 2]
    return F


F = fib_list(M)
s = 0.0
for k in range(1, M + 1):
    a = k ** 0.5
    b = F[k] ** 0.5
    s += C_opt(N, a, b)

print(f"{s:.8f}")