Problem 406: Guessing Game

Project Euler Problem 406 Solution

EulerSolve provides an optimized solution for Project Euler Problem 406, Guessing Game, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For positive real costs $a$ and $b$, let $C(n,a,b)$ denote the smallest budget $c$ that guarantees success in an ordered guessing game with at least $n$ candidates: after each guess, one non-equal answer consumes cost $a$ and the other consumes cost $b$. In Problem 406 we must evaluate $$\sum_{k=1}^{30} C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right),\qquad F_1=F_2=1,\quad F_k=F_{k-1}+F_{k-2}.$$ A direct search over strategies is hopeless, so the solution converts the game into a lattice dynamic program that counts how many ordered candidates a fixed budget can handle. Mathematical Approach Define $K(c,a,b)$ as the largest number of ordered candidates that can always be distinguished with total cost at most $c$. Once $K$ is known, the desired threshold value is $$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$ The implementation therefore solves two subproblems: compute $K(c,a,b)$ for a fixed budget, then binary-search the smallest $c$ for which $K(c,a,b)$ reaches the target $n$. Step 1: State Space Under a Fixed Budget Suppose that along the current path of the decision tree we have already seen $i$ answers of the first type and $j$ answers of the second type....

Detailed mathematical approach

Problem Summary

A hidden integer is chosen from $\{1,2,\dots,n\}$ and we must find it by naming numbers. Each guess is answered in one of three ways: our guess is lower than the hidden number, at a cost of $a$; it is higher, at a cost of $b$; or it is the hidden number, which ends the game free. A guess may be chosen after seeing the previous answers, and a strategy costs what it spends on the worst possible hidden number; an optimal strategy minimises that worst case, and $C(n,a,b)$ is the cost it achieves. The statement gives $C(5,2,3)=5$, $C(500,\sqrt2,\sqrt3)=13.22073197\dots$, $C(20000,5,7)=82$ and $C(2000000,\sqrt5,\sqrt7)=49.63755955\dots$, and asks for

$$\sum_{k=1}^{30}C\bigl(10^{12},\sqrt k,\sqrt{F_k}\bigr),$$

rounded to eight decimal places, where $F_1=F_2=1$ and $F_k=F_{k-1}+F_{k-2}$. ^[1]

The whole solution in one sentence: count the sequences of paid answers that fit inside a proposed budget, the empty sequence included, and find the smallest budget whose count reaches the number of candidates.

Mathematical Approach

1. The example of the statement

Take $n=5$, $a=2$, $b=3$ and ask $2$ first, then $4$ if $2$ was too low. The five numbers $1,\dots,5$ then cost $3$, $0$, $2+3$, $2$ and $2+2$; the worst is $5$, and the statement says no strategy does better, so $C(5,2,3)=5$. Two features of this tiny game drive everything below: each guess cuts the surviving numbers into a lower and an upper part, and an outcome's cost depends only on how many "lower" and how many "higher" answers led to it, not on their order.

2. Only the size of the surviving block matters

After any sequence of answers the numbers still possible form a block of consecutive integers: $\{1,\dots,n\}$ is one, and an answer to a guess $g$ replaces the block $\{l,\dots,r\}$ by $\{g+1,\dots,r\}$ or by $\{l,\dots,g-1\}$, blocks again. We may also assume $l\le g\le r$, since a guess with $g\lt l$ can only be answered "your guess is lower" and one with $g\gt r$ only "your guess is higher"; either answer costs something and removes nothing, so such a guess can be deleted. Writing $g$ as the $t$-th member of a block of $m$ numbers, the branches hold $t-1$ numbers below and $m-t$ above. Nothing there mentions $l$ or $r$, so the optimal remaining cost depends only on $m$. Call it $W(m)$: then $W(1)=0$, $C(n,a,b)=W(n)$, and

$$\begin{aligned}W(m)=\min_{1\le t\le m}\max\bigl(&b+W(t-1),\\&a+W(m-t)\bigr),\end{aligned}$$

where a branch holding no number contributes $0$ rather than $a$ or $b$.

3. A strategy is a binary search tree

The recurrence is easier to understand as a tree. A strategy for a block of $m$ numbers is a rooted binary tree: the root is the first guess, its left child the strategy used after "your guess is higher", its right child the one used after "your guess is lower". By Section 2 the root guess is the $t$-th number of the block, the left subtree handles the $t-1$ numbers below it and the right subtree the $m-t$ above it. Reading it in order — left subtree, node, right subtree — therefore lists the $m$ numbers increasingly, the defining property of a binary search tree. ^[2] Conversely, any binary tree with $m$ nodes becomes a strategy once its in-order traversal names the numbers. The two are the same objects, and each number is identified at its own node: one node, one number.

4. What a node costs

Price the edges: a step to a right child costs $a$, since it follows "your guess is lower", and a step to a left child costs $b$. If the path from the root to a node uses $i$ right steps and $j$ left steps, the answers along it cost

$$ia+jb,$$

and that is the total paid when the guess at that node proves correct, a correct guess being free. The worst-case cost of a strategy is thus the largest $ia+jb$ over its nodes, and a strategy stays within a budget $c$ exactly when every node satisfies $ia+jb\le c$. Only the pair $(i,j)$ matters, never the order of the steps; call $(i,j)$ the position of the node, and call it affordable when $ia+jb\le c$.

5. The largest affordable tree

Define

$$K(c,a,b)=\sum_{ia+jb\le c}\binom{i+j}{i},$$

summed over the non-negative integer pairs with $ia+jb\le c$. The binomial coefficient counts the paths reaching $(i,j)$: a path is a word of right and left steps, and choosing which $i$ go right fixes it — the standard count of monotone lattice paths. ^[6]

Since $a,b\gt0$, neither $i$ nor $j$ decreases along a path, so every prefix of an affordable word is affordable. The set $T$ of all affordable words is thus closed under prefixes, which is what makes it a tree: the empty word is its root, and $w$ has the children $wR$ and $wL$ whenever those are affordable. Any tree with only affordable nodes embeds into $T$ by reading off each node's step word, so $T$ is the largest of them, and grouping its words by position gives $|T|=K(c,a,b)$.

Hence the equivalence the solution rests on. A strategy for $n$ numbers within $c$ is an affordable tree with $n$ nodes, which forces $K(c,a,b)\ge n$. Conversely, if $K(c,a,b)\ge n$, delete leaves of $T$ one at a time until $n$ nodes remain — deleting a leaf keeps the set prefix-closed and raises no cost — and label the survivors $1,\dots,n$ in order; Section 3 turns that tree into a strategy within $c$. So

$$C(n,a,b)\le c\iff K(c,a,b)\ge n.$$

6. Worked example: $a=2$, $b=3$

At $c=5$ the affordable positions are $(0,0)$, $(1,0)$, $(2,0)$, $(0,1)$ and $(1,1)$, with path counts $1,1,1,1$ and $\binom21=2$, so $K(5,2,3)=6$. At $c=4$ the position $(1,1)$ costs $5$ and drops out, leaving $K(4,2,3)=4$. Every cost is a sum $2i+3j$, so no budget between $4$ and $5$ buys anything new: five numbers need exactly $5$, as the statement says, and six need $5$ too. Letting $c$ run from $0$ to $10$ gives the capacities

$$1,1,2,3,4,6,8,11,15,20,27,$$

from which one reads $C(7,2,3)=6$ and $C(12,2,3)=8$. The six-node tree at $c=5$ has the shape of the strategy of Section 1 with one node added, but the labels shift: reading it in order and labelling $1,\dots,6$ makes the root $3$, its left child $1$ with right child $2$, and its right child $5$ with children $4$ and $6$. The nodes $2$ and $4$ both sit at $(1,1)$ and cost $5$ — the two orders of spending $2+3$, which is what $\binom21=2$ counts.

7. The minimum is attained, and at a lattice value

The capacity is a staircase in $c$: it never decreases, since a larger budget only adds affordable positions, and it changes only when $c$ crosses a value $ia+jb$. Those values are locally finite — below a bound $B$ only $i\le\lfloor B/a\rfloor$ and $j\le\lfloor B/b\rfloor$ occur — and a chain of $n$ nodes using only the cheaper answer already succeeds at $B=(n-1)\min(a,b)$. Among the finitely many values up to that $B$ there is therefore a smallest with $K\ge n$, so the minimum is attained:

$$C(n,a,b)=i^{*}a+j^{*}b.$$

That is why the checkpoints are exact algebraic numbers. Computed exactly they are $1\cdot2+1\cdot3$, $2\sqrt2+6\sqrt3$, $1\cdot5+11\cdot7$ and $8\sqrt5+12\sqrt7$ — the four values of the statement, in its order. Note also $\binom{i+j}{i}=\binom{i+j}{j}$, so exchanging $a$ and $b$ leaves $K$, and therefore $C$, unchanged.

8. The backward recurrence

Summing $K$ over the lattice directly needs binomial coefficients whose upper index runs into the thousands. The tree $T$ gives a cheaper route, but the definition needs care, since several words share one position: for $a=2$, $b=3$, $c=5$ both $RL$ and $LR$ reach $(1,1)$. Let $D_c(i,j)$ be the number of nodes in the subtree of $T$ rooted at one affordable word of position $(i,j)$, itself included; all such words have the same affordable continuations, so the count depends only on $(i,j)$. Here $D_5(1,1)=1$, as both those words are leaves. An unaffordable position has $D_c(i,j)=0$, and an affordable subtree is its root plus its two child subtrees, so

$$D_c(i,j)=1+D_c(i+1,j)+D_c(i,j+1)$$

when $ia+jb\le c$, and $K(c,a,b)=D_c(0,0)$. The costs being positive, every affordable position has $i\le\lfloor c/a\rfloor$ and $j\le\lfloor c/b\rfloor$, so the table is finite, and filling it with both $i$ and $j$ decreasing makes both successors available when a cell is reached, at two additions per affordable cell and nothing for the rest.

One refinement makes the numbers manageable. The search outside only asks whether $D_c(0,0)\ge n$, so a cell may be frozen at $n$ once it reaches $n$: larger values are never needed, and freezing can only pull other cells down to $n$, never below. Without it the counts explode — at the largest budget tried for $k=12$ the unfrozen $D_c(0,0)$ has $23$ digits, over three thousand times $2^{64}$.

9. Worked example: $C(500,\sqrt2,\sqrt3)$

Take $c=2\sqrt2+6\sqrt3=13.2207\dots$, so $\lfloor c/\sqrt2\rfloor=9$ and $\lfloor c/\sqrt3\rfloor=7$. Group the affordable positions by the number $j$ of downward answers. In row $j$ the affordable $i$ run from $0$ to some $I_j$, and the hockey-stick identity ^[3]

$$\sum_{i=0}^{m}\binom{i+j}{i}=\binom{m+j+1}{j+1}$$

collapses each row to one binomial coefficient. The eight rows $j=0,\dots,7$ have $I_j=9,8,6,5,4,3,2,0$ and contribute

$$10,45,84,126,126,84,36,1,$$

a total of $512$. The next smaller lattice value, $8\sqrt2+\sqrt3=13.0457\dots$, gives only $484$, so $484\lt500\le512$ pins the threshold at $2\sqrt2+6\sqrt3$, the checkpoint of the statement. The identity turns $K$ into a sum of $\lfloor c/b\rfloor+1$ binomial coefficients, which is how every capacity here was checked twice over, independently of Section 8.

10. Commensurable costs, and two terms for free

Call the costs commensurable when $a=Ad$ and $b=Bd$ for positive integers $A,B$ and a unit $d\gt0$; every node cost is then a multiple of $d$, and a one-dimensional table indexed by the budget in units of $d$ suffices. Splitting the affordable words into the empty word and those starting with an upward or a downward answer gives, for any positive costs,

$$K(c)=1+K(c-a)+K(c-b),$$

with $K(c)=0$ for negative $c$. Related generalised Fibonacci recurrences appear in asymmetric search where both answers are paid; here the extra $1$ is the number pinned down by the free correct guess at the node itself. ^[4] For $a=b=1$ it yields $K(c)=2^{\lfloor c\rfloor+1}-1$: $q$ questions separate $2^{q}-1$ numbers. Plain binary search over $10^{12}$ numbers needs $q=40$, ^[5] leaving $39$ wrong answers at worst, so

$$C(10^{12},1,1)=39,\qquad C(10^{12},\sqrt5,\sqrt5)=39\sqrt5.$$

These are the terms $k=1$ and $k=5$, since $F_1=1$ and $F_5=5$, and the only commensurable pairs in range: the ratio $\sqrt{k}/\sqrt{F_k}$ equals $\sqrt{kF_k}/F_k$, rational exactly when $kF_k$ is a perfect square, and for $1\le k\le30$ only $k=1,5$ qualify. For the other $28$ no unit $d$ makes both costs integral, so there is no one-dimensional grid to index and the table of Section 8 is the right tool.

11. From capacity to cost

Monotonicity makes the threshold a bisection problem: double $c$ from $1$ until the capacity reaches $n$, then halve the bracket repeatedly, keeping the upper end whenever the capacity there still reaches $n$. A complete tree of depth $d$ has $2^{d+1}-1$ nodes and costs at most $d\max(a,b)$, so capacity grows at least exponentially in $c$ and the doubling stops after $6$ to $13$ steps here. Finally sum the $30$ thresholds and round to eight decimals.

How the Code Works

In the C++ program ^[8], Options holds the target $n$, by default $10^{12}$, and whether to run the checkpoints; parse_arguments reads --n= and --skip-checkpoints and rejects an unknown flag or $n=0$.

capacity_with_budget(c, a, b, cap) is Section 8. It sets imax to $\lfloor c/a\rfloor$ and jmax to $\lfloor c/b\rfloor$, allocates one flat std::vector of $(\mathtt{imax}+2)(\mathtt{jmax}+2)$ counters addressed by the lambda at, and sweeps $i$ from imax down to $0$ and, inside that, $j$ from jmax down to $0$. The extra row and column are the zero boundary, so at(i+1, j) and at(i, j+1) are in range and already final. The test is ai + j*b <= c + eps with eps equal to $10^{-16}(1+c)$, a guard against the rounding of $ia+jb$ for irrational costs, and the sum is formed in __uint128_t and clamped to cap before storing — the freezing of Section 8.

C_value(n, a, b) is Section 11: it doubles hi from $1$ until the capacity reaches $n$, performs exactly $90$ bisection iterations and returns hi. run_checkpoints compares it with the four values of the statement through nearly_equal, a relative test with tolerance $10^{-14}$ for the two integer checkpoints and $5\cdot10^{-10}$ for the two truncated decimals. solve_sum builds fib[1..30] and adds the thresholds; main prints the total with std::fixed and setprecision(8) after casting to double.

Python mirrors the C++ almost line for line on a flat list, its unbounded integers doing the work of __uint128_t, and formats with "{:.8f}"; Java's capacityWithBudget uses a long[] with double costs, and String.format with Locale.US forces a decimal point. In Java the clamp is what keeps the counters legal: a long could not hold the unfrozen counts of Section 8, whereas $1+2n$ fits. Both ports fix $n$ inside solve and print the sum without running the checkpoints, so only the C++ program checks itself.

Precision differs too. C++ uses long double for the costs and the accumulator where the others use double; what that buys depends on the platform, since long double is extended precision on x86 but has exactly the precision of double on 64-bit ARM macOS. ^[7] On the machine used here it is the latter, and the three were measured to print identical output.

Complexity and Verification

Write $I=\lfloor c/a\rfloor$ and $J=\lfloor c/b\rfloor$. One capacity evaluation zeroes $(I+2)(J+2)$ counters and visits $(I+1)(J+1)$ of them, so for $c\ge\max(a,b)$ time and memory are both $O(c^2/(ab))$. A threshold costs the doublings plus the $90$ iterations: $97$ to $104$ evaluations, $3012$ over all $30$ values of $k$. Instrumenting those searches puts the largest table at $k=28$, budget $8192$: $1550$ rows, $16$ columns, $24800$ counters, $198400$ bytes. In all $8\,961\,644$ counters are zeroed and $8\,189\,427$ cells visited; measured here, C++ takes about $0.01$ s, Java $0.05$ s, Python $0.84$ s.

The $90$ iterations are generous: the widest bracket is $8192$ and a double has a $53$-bit significand, so after about $52$ steps the midpoint rounds to an end of the bracket. The error needs care. The tolerance eps relaxes only the comparison, not the bounds $I$ and $J$, which still come from $c$, so the computed capacity lies between $K(c)$ and $K(c+\mathtt{eps})$ and nothing stronger holds: one unit in the last place below $c=1$, with $a=b=1$, it returns $1$ where $K(c+\mathtt{eps})=3$. That bracket does keep the returned threshold within eps below the exact one, but rounding $\sqrt k$ and $\sqrt{F_k}$ adds an error of either sign — the same code puts $C(2,\sqrt2,\sqrt3)$ about $10^{-16}$ above $\sqrt2$. Against exact values the worst of the $30$ terms is off by $1.3\cdot10^{-12}$ and the sum by about $5\cdot10^{-12}$, while the exact sum lies some $3\cdot10^{-9}$ from the nearest eight-decimal midpoint: the printed digits are safe by a factor near $600$, comfortable but not a margin to enlarge $n$ with carelessly.

The checks below ran in exact rational arithmetic. For every $n\le12$ and the cost pairs $(2,3)$, $(3,1)$, $(1,1)$, $(5,7)$, $(7/3,11/5)$, three independent methods agree: an exhaustive search whose state is an arbitrary subset of $\{1,\dots,n\}$ and whose guesses range over all of it, the block recurrence $W(m)$, and the lattice threshold of Section 5. On those five pairs and every half-integer budget to $30$ — $305$ tests — the recurrence of Section 8 equals $\sum\binom{i+j}{i}$; on six pairs and half-integer budgets to $40$ — $486$ tests — the hockey-stick form equals both, as it does at all $30$ thresholds of the target instance. For integer budgets to $12$, where no affordable word exceeds $12$ steps since every cost is at least $1$, enumerating the words literally agrees too. All four checkpoints come out right, with capacities $6$, $512$, $22358$, $2041334$ at the thresholds against $4$, $484$, $19327$, $1915364$ one lattice value lower.

The $30$ thresholds were then recomputed outside the published programs in integer arithmetic: subtract two lattice costs; equal signs or a zero among the coefficients of $\sqrt p$ and $\sqrt q$ settle the comparison at once, and opposite signs are decided by moving one term across and comparing squares. Evaluated to $80$ digits these give the errors above, and their sum rounds to the eight decimals all three programs print. One edge case is imperfect: for $n=1$ no question is needed and $C=0$, but the bisection only approaches $0$ from above and returns $2^{-90}$, about $8\cdot10^{-28}$ — invisible at eight decimals and harmless for $n=10^{12}$.

Footnotes and References

The references supply the background facts used above; the reduction to blocks, the capacity formula and the proof that the threshold is a lattice value are derived here.

Project Euler 406 — Guessing Game. The official statement gives the hidden number in {1, …, n}, the three answers with their costs a, b and zero, and the rule that an optimal strategy minimises the worst-case total. It works n = 5, a = 2, b = 3 to a worst case of 5, lists the four values of C quoted above, defines F₁ = F₂ = 1, and asks for the sum to eight decimal places.
Wikipedia — Binary search tree. The ordering property — every key in a node's left subtree smaller than the node's key, every key in its right subtree larger — makes an in-order traversal visit the keys in non-decreasing order, which is what Section 3 uses.
Wikipedia — Hockey-stick identity. The identity is the sum of C(i, r) for i from r to n equalling C(n + 1, r + 1); the article derives the mirror image, the sum of C(j + r, j) for j from 0 to n − r equalling C(n + 1, n − r), which with r = j and n − r = m is the row formula of Section 9.
P. S. Efraimidis, (α, β) Fibonacci Search, arXiv:1012.0259. The paper searches a sorted array when a comparison costs α or β by outcome, both strictly positive, so no outcome is free: Proposition 4 counts the leaves of a complete decision tree of level k by a generalised Fibonacci sequence G(k), Proposition 5 makes the least k with G(k) ≥ n a lower bound, and Proposition 6 argues attainment. The free correct guess here makes every node, not only a leaf, carry a candidate.
Wikipedia — Binary search. The worst case on n elements is ⌊log₂(n)⌋ + 1 iterations of the comparison loop, and the comparison tree shows no algorithm comparing elements uses fewer levels; for n = 10¹² that is the 40 guesses of Section 10.
Wikipedia — Lattice path. A north-east lattice path uses only north and east steps, and the number of them from the origin to (n, k) is C(n + k, n), the number of ways of choosing which steps go east — the count of Section 5.
Wikipedia — Long double. The representation is platform-dependent: the 80-bit extended type on most x86 compilers, a synonym for double on Microsoft Visual C++ and on 32-bit ARM, and on 64-bit ARM under Windows and macOS; quadruple precision on some platforms, double-double on some PowerPC systems. It cannot be assumed wider than double.
C++ — Euler406.cpp. The linked immutable revision contains capacity_with_budget, C_value, nearly_equal, run_checkpoints and solve_sum, and is the implementation record for this article. The exact recomputation of the thresholds is additional validation, not a check packaged in that file.

Problem 406 source code

C++

#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    u64 n = 1000000000000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = static_cast<u64>(std::stoull(tail));
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.n >= 1;
}

u64 capacity_with_budget(const long double c, const long double a, const long double b, const u64 cap) {
    const int imax = static_cast<int>(std::floor(c / a));
    const int jmax = static_cast<int>(std::floor(c / b));
    const int cols = jmax + 2;

    std::vector<u64> dp(static_cast<std::size_t>((imax + 2) * cols), 0ULL);
    auto at = [&](const int i, const int j) -> u64& {
        return dp[static_cast<std::size_t>(i * cols + j)];
    };

    const long double eps = 1e-16L * (1.0L + c);
    for (int i = imax; i >= 0; --i) {
        const long double ai = static_cast<long double>(i) * a;
        for (int j = jmax; j >= 0; --j) {
            if (ai + static_cast<long double>(j) * b <= c + eps) {
                __uint128_t v = 1;
                v += at(i + 1, j);
                v += at(i, j + 1);
                if (v > cap) {
                    v = cap;
                }
                at(i, j) = static_cast<u64>(v);
            }
        }
    }

    return at(0, 0);
}

long double C_value(const u64 n, const long double a, const long double b) {
    long double lo = 0.0L;
    long double hi = 1.0L;
    while (capacity_with_budget(hi, a, b, n) < n) {
        hi *= 2.0L;
    }

    for (int it = 0; it < 90; ++it) {
        const long double mid = (lo + hi) / 2.0L;
        if (capacity_with_budget(mid, a, b, n) >= n) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    return hi;
}

bool nearly_equal(const long double a, const long double b, const long double rel_tol) {
    const long double scale = std::max(std::fabsl(a), std::fabsl(b));
    if (scale == 0.0L) {
        return true;
    }
    return std::fabsl(a - b) <= rel_tol * scale;
}

bool run_checkpoints() {
    const long double c1 = C_value(5, 2.0L, 3.0L);
    if (!nearly_equal(c1, 5.0L, 1e-14L)) {
        std::cerr << "Checkpoint failed: C(5,2,3)\n";
        return false;
    }

    const long double c2 = C_value(500, std::sqrt(2.0L), std::sqrt(3.0L));
    if (!nearly_equal(c2, 13.22073197L, 5e-10L)) {
        std::cerr << "Checkpoint failed: C(500,sqrt2,sqrt3)\n";
        return false;
    }

    const long double c3 = C_value(20000, 5.0L, 7.0L);
    if (!nearly_equal(c3, 82.0L, 1e-14L)) {
        std::cerr << "Checkpoint failed: C(20000,5,7)\n";
        return false;
    }

    const long double c4 = C_value(2000000, std::sqrt(5.0L), std::sqrt(7.0L));
    if (!nearly_equal(c4, 49.63755955L, 5e-10L)) {
        std::cerr << "Checkpoint failed: C(2000000,sqrt5,sqrt7)\n";
        return false;
    }

    return true;
}

long double solve_sum(const u64 n) {
    std::vector<u64> fib(31, 0ULL);
    fib[1] = 1ULL;
    fib[2] = 1ULL;
    for (int k = 3; k <= 30; ++k) {
        fib[static_cast<std::size_t>(k)] = fib[static_cast<std::size_t>(k - 1)] + fib[static_cast<std::size_t>(k - 2)];
    }

    long double ans = 0.0L;
    for (int k = 1; k <= 30; ++k) {
        const long double a = std::sqrt(static_cast<long double>(k));
        const long double b = std::sqrt(static_cast<long double>(fib[static_cast<std::size_t>(k)]));
        ans += C_value(n, a, b);
    }
    return ans;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const long double answer = solve_sum(options.n);
    std::cout << std::fixed << std::setprecision(8) << static_cast<double>(answer) << '\n';
    return 0;
}

Python

import math

def capacity_with_budget(c, a, b, cap):
    imax = int(c / a)
    jmax = int(c / b)
    cols = jmax + 2

    dp = [0] * ((imax + 2) * cols)
    def at(i, j):
        return i * cols + j

    eps = 1e-16 * (1.0 + c)
    for i in range(imax, -1, -1):
        ai = i * a
        for j in range(jmax, -1, -1):
            if ai + j * b <= c + eps:
                v = 1 + dp[at(i + 1, j)] + dp[at(i, j + 1)]
                if v > cap:
                    v = cap
                dp[at(i, j)] = v

    return dp[at(0, 0)]

def C_value(n, a, b):
    lo = 0.0
    hi = 1.0
    while capacity_with_budget(hi, a, b, n) < n:
        hi *= 2.0

    for _ in range(90):
        mid = (lo + hi) / 2.0
        if capacity_with_budget(mid, a, b, n) >= n:
            hi = mid
        else:
            lo = mid

    return hi

def solve():
    n = 1000000000000
    fib = [0] * 31
    fib[1] = 1
    fib[2] = 1
    for k in range(3, 31):
        fib[k] = fib[k - 1] + fib[k - 2]

    ans = 0.0
    for k in range(1, 31):
        a = math.sqrt(k)
        b = math.sqrt(fib[k])
        ans += C_value(n, a, b)
        
    return "{:.8f}".format(ans)

if __name__ == '__main__':
    print(solve())

Java

public class Euler406 {
    private static long capacityWithBudget(double c, double a, double b, long cap) {
        int imax = (int) Math.floor(c / a);
        int jmax = (int) Math.floor(c / b);
        int cols = jmax + 2;

        long[] dp = new long[(imax + 2) * cols];
        double eps = 1e-16 * (1.0 + c);

        for (int i = imax; i >= 0; --i) {
            double ai = i * a;
            for (int j = jmax; j >= 0; --j) {
                if (ai + j * b <= c + eps) {
                    long v = 1 + dp[(i + 1) * cols + j] + dp[i * cols + j + 1];
                    if (v > cap) {
                        v = cap;
                    }
                    dp[i * cols + j] = v;
                }
            }
        }

        return dp[0];
    }

    private static double cValue(long n, double a, double b) {
        double lo = 0.0;
        double hi = 1.0;
        while (capacityWithBudget(hi, a, b, n) < n) {
            hi *= 2.0;
        }

        for (int it = 0; it < 90; ++it) {
            double mid = (lo + hi) / 2.0;
            if (capacityWithBudget(mid, a, b, n) >= n) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        return hi;
    }

    public static String solve() {
        long n = 1000000000000L;
        long[] fib = new long[31];
        fib[1] = 1;
        fib[2] = 1;
        for (int k = 3; k <= 30; ++k) {
            fib[k] = fib[k - 1] + fib[k - 2];
        }

        double ans = 0.0;
        for (int k = 1; k <= 30; ++k) {
            double a = Math.sqrt(k);
            double b = Math.sqrt(fib[k]);
            ans += cValue(n, a, b);
        }

        return String.format(java.util.Locale.US, "%.8f", ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}