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.
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\).
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. The spent cost is then
$$ia+jb.$$
Such a state is still usable exactly when
$$ia+jb\le c.$$
This gives the finite feasible lattice region
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
Now let \(D_c(i,j)\) be the maximum number of ordered candidates that can still be resolved from state \((i,j)\). Outside the feasible region there is no remaining budget, so
$$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c.$$
At a feasible state \((i,j)\), the next guess picks one pivot candidate. That pivot itself contributes one distinguishable value. If the hidden value falls on the \(a\)-cost branch, the next state becomes \((i+1,j)\); if it falls on the \(b\)-cost branch, the next state becomes \((i,j+1)\).
Therefore every strategy rooted at \((i,j)\) can distinguish at most
$$1+D_c(i+1,j)+D_c(i,j+1)$$
candidates.
Conversely, if the left continuation can handle \(L=D_c(i+1,j)\) candidates and the right continuation can handle \(R=D_c(i,j+1)\) candidates, then an ordered block of length \(L+1+R\) can be handled exactly: guess the \((L+1)\)-st candidate, use the left strategy on the lower block, and the right strategy on the upper block.
Hence the upper bound is attainable, so the recurrence is exact:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
The quantity needed by the outer search is simply
$$K(c,a,b)=D_c(0,0).$$
The checkpoint \(C(5,2,3)=5\) illustrates the mechanism well.
For \(c=4\), the feasible states are \((0,0),(1,0),(2,0),(0,1)\). Working backward gives
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
So a budget of \(4\) can guarantee only \(K(4,2,3)=4\) candidates.
For \(c=5\), the extra feasible state \((1,1)\) appears, and now
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
Thus \(K(5,2,3)=6\ge 5\). Since \(4\) is insufficient and \(5\) is sufficient, we obtain
$$C(5,2,3)=5.$$
If \(c_1\le c_2\), then \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). Every state available with budget \(c_1\) is also available with budget \(c_2\), so
$$K(c_1,a,b)\le K(c_2,a,b).$$
That monotonicity makes \(C(n,a,b)\) a standard “binary search on the answer” problem. The implementation first doubles an upper bound \(1,2,4,8,\dots\) until the capacity reaches \(n\), and then performs 90 bisection steps to isolate the minimal sufficient budget to high precision.
After computing the Fibonacci numbers \(F_1,\dots,F_{30}\), the algorithm forms the 30 parameter pairs
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
For each pair it computes the threshold budget \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\), then sums all 30 values. The mathematical burden is therefore concentrated entirely in evaluating the capacity function \(K(c,a,b)\) efficiently.
For one fixed budget \(c\), the implementation sets
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
allocates a rectangular DP table of size \((i_{\max}+2)\times(j_{\max}+2)\), and fills it from bottom-right toward top-left so that the two successor states are already known when a cell is updated.
A tiny tolerance \(\varepsilon=10^{-16}(1+c)\) is added in the feasibility test \(ia+jb\le c+\varepsilon\) to protect against floating-point roundoff when \(a\) and \(b\) are irrational square roots.
Each DP value is also clamped at the target \(n\). This does not change the answer, because the outer search only asks whether the capacity is at least \(n\); once a cell reaches \(n\), larger values are irrelevant. Saturation prevents overflow and keeps the arithmetic numerically stable.
The C++, Python, and Java implementations all follow this same plan: build Fibonacci numbers, solve 30 independent threshold searches, and print the final sum to eight decimal places.
For one evaluation of \(K(c,a,b)\), the table dimensions are
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
so the dynamic program uses \(O(IJ)\) time and \(O(IJ)\) memory.
To obtain \(C(n,a,b)\), exponential bracketing uses \(O(\log C(n,a,b))\) capacity evaluations, followed by exactly 90 bisection evaluations. Since the Project Euler instance has only 30 parameter pairs, the total runtime is the sum of these fixed-cost searches over \(k=1,\dots,30\).
Für positive reelle Kosten \(a\) und \(b\) bezeichne \(C(n,a,b)\) das kleinste Budget \(c\), mit dem man in einem geordneten Ratespiel bei mindestens \(n\) Kandidaten stets erfolgreich ist: Nach jedem Tipp kostet der eine Nicht-Gleichheitsfall \(a\), der andere \(b\). In Problem 406 ist zu berechnen
$$\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}.$$
Eine direkte Suche über alle Entscheidungsbäume ist unmöglich. Daher übersetzt die Lösung das Spiel in ein Gitter-DP, das zählt, wie viele geordnete Kandidaten ein festes Budget tragen kann.
Definiere \(K(c,a,b)\) als die größte Anzahl geordneter Kandidaten, die sich mit Gesamtkosten höchstens \(c\) sicher unterscheiden lassen. Ist \(K\) bekannt, dann ist der gesuchte Schwellenwert
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$
Die Implementierung löst also zwei Teilprobleme: erstens \(K(c,a,b)\) für festes Budget bestimmen, zweitens das kleinste \(c\) per Binärsuche finden, bei dem \(K(c,a,b)\) den Zielwert \(n\) erreicht.
Angenommen, auf dem aktuellen Pfad des Entscheidungsbaums sind bereits \(i\) Antworten des ersten Typs und \(j\) Antworten des zweiten Typs aufgetreten. Dann betragen die bisher verbrauchten Kosten
$$ia+jb.$$
Ein solcher Zustand ist genau dann noch zulässig, wenn
$$ia+jb\le c.$$
Damit entsteht die endliche zulässige Gitterregion
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
Sei nun \(D_c(i,j)\) die maximale Zahl geordneter Kandidaten, die sich aus dem Zustand \((i,j)\) noch sicher auflösen lässt. Außerhalb der zulässigen Region bleibt kein Budget mehr übrig, also gilt
$$D_c(i,j)=0\qquad\text{für }(i,j)\notin \mathcal{R}_c.$$
In einem zulässigen Zustand \((i,j)\) wählt der nächste Tipp einen Pivot-Kandidaten. Dieser Pivot selbst liefert einen eindeutig unterscheidbaren Wert. Fällt der gesuchte Wert in den \(a\)-Kosten-Zweig, geht man nach \((i+1,j)\); fällt er in den \(b\)-Kosten-Zweig, geht man nach \((i,j+1)\).
Jede Strategie mit Wurzel \((i,j)\) kann daher höchstens
$$1+D_c(i+1,j)+D_c(i,j+1)$$
Kandidaten unterscheiden.
Umgekehrt ist diese Schranke erreichbar: Wenn die linke Fortsetzung \(L=D_c(i+1,j)\) Kandidaten tragen kann und die rechte Fortsetzung \(R=D_c(i,j+1)\), dann lässt sich ein geordneter Block der Länge \(L+1+R\) exakt behandeln. Man rät den \((L+1)\)-ten Kandidaten, benutzt links die linke Strategie und rechts die rechte Strategie.
Damit ist die Rekurrenz nicht nur eine Schranke, sondern exakt:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
Die für die äußere Suche benötigte Kapazität ist also
$$K(c,a,b)=D_c(0,0).$$
Der Kontrollwert \(C(5,2,3)=5\) zeigt den Mechanismus gut.
Für \(c=4\) sind die zulässigen Zustände \((0,0),(1,0),(2,0),(0,1)\). Rückwärts ausgewertet ergibt das
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
Mit Budget \(4\) kann man also nur \(K(4,2,3)=4\) Kandidaten sicher behandeln.
Für \(c=5\) kommt der zusätzliche Zustand \((1,1)\) hinzu, und es gilt nun
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
Somit ist \(K(5,2,3)=6\ge 5\). Da \(4\) nicht reicht und \(5\) ausreicht, folgt
$$C(5,2,3)=5.$$
Aus \(c_1\le c_2\) folgt \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). Jeder mit \(c_1\) zulässige Zustand ist auch mit \(c_2\) zulässig, also
$$K(c_1,a,b)\le K(c_2,a,b).$$
Gerade diese Monotonie macht \(C(n,a,b)\) zu einem klassischen Problem der Binärsuche auf der Antwort. Die Implementierung verdoppelt zunächst eine obere Schranke \(1,2,4,8,\dots\), bis die Kapazität mindestens \(n\) ist, und führt danach 90 Bisektionsschritte aus.
Nachdem die Fibonacci-Zahlen \(F_1,\dots,F_{30}\) berechnet sind, entstehen die 30 Parameterpaare
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
Für jedes Paar wird der Schwellenwert \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\) bestimmt, anschließend werden alle 30 Werte addiert. Die gesamte Mathematik konzentriert sich also auf die effiziente Auswertung der Kapazitätsfunktion \(K(c,a,b)\).
Für ein festes Budget \(c\) setzt die Implementierung
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
legt eine rechteckige DP-Tabelle der Größe \((i_{\max}+2)\times(j_{\max}+2)\) an und füllt sie von rechts unten nach links oben, sodass die beiden Nachfolgerwerte beim Aktualisieren bereits bekannt sind.
In der Zulässigkeitsprüfung \(ia+jb\le c+\varepsilon\) wird eine winzige Toleranz \(\varepsilon=10^{-16}(1+c)\) addiert, damit Rundungsfehler bei irrationalen Quadratwurzeln die Gittergrenze nicht falsch klassifizieren.
Außerdem wird jeder DP-Wert bei \(n\) abgeschnitten. Das ändert das Ergebnis nicht, weil die äußere Suche nur prüft, ob die Kapazität mindestens \(n\) erreicht. Größere Werte sind also irrelevant. Diese Sättigung verhindert Überläufe und hält die Zahlen stabil.
Die C++-, Python- und Java-Implementierungen verwenden genau dieses Schema: Fibonacci-Zahlen erzeugen, 30 unabhängige Schwellensuchen ausführen und die Endsumme mit acht Nachkommastellen ausgeben.
Für eine Auswertung von \(K(c,a,b)\) haben die Tabellendimensionen die Form
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
weshalb das dynamische Programm \(O(IJ)\) Zeit und \(O(IJ)\) Speicher benötigt.
Um \(C(n,a,b)\) zu erhalten, braucht die exponentielle Schrankenfindung \(O(\log C(n,a,b))\) Kapazitätsauswertungen; danach folgen genau 90 Bisektionsauswertungen. Da die Euler-Aufgabe nur 30 Parameterpaare besitzt, ist die Gesamtlaufzeit die Summe dieser festen Suchkosten über \(k=1,\dots,30\).
Pozitif reel maliyetler \(a\) ve \(b\) için \(C(n,a,b)\), en az \(n\) adaylı sıralı bir tahmin oyununda başarıyı garanti eden en küçük bütçe \(c\) olsun: her tahminden sonra eşit olmama durumlarının biri \(a\), diğeri \(b\) maliyet üretir. Problem 406'da hesaplanması gereken ifade
$$\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}.$$
Tüm stratejileri doğrudan taramak imkansızdır. Bu yüzden çözüm, oyunu sabit bir bütçenin kaç sıralı adayı ayırt etmeye yettiğini sayan bir kafes tipi dinamik programa dönüştürür.
\(K(c,a,b)\), toplam maliyeti en fazla \(c\) olacak şekilde her zaman ayırt edilebilen en büyük sıralı aday sayısı olsun. Bu fonksiyon bilindiğinde aranan eşik değer
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}$$
şeklindedir. Dolayısıyla uygulama iki işi yapar: önce sabit bütçe için \(K(c,a,b)\)'yi hesaplar, sonra \(K(c,a,b)\ge n\) yapan en küçük \(c\)'yi ikili aramayla bulur.
Karar ağacının mevcut yolunda şimdiye kadar birinci tipten \(i\), ikinci tipten \(j\) cevap alındığını düşünelim. O ana kadar harcanan maliyet
$$ia+jb$$
olur. Bu durum ancak
$$ia+jb\le c$$
ise kullanılabilir durumdadır.
Böylece sonlu uygun kafes bölgesi
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}$$
elde edilir. Şimdi \(D_c(i,j)\), \((i,j)\) durumundan sonra hâlâ kesin olarak ayırt edilebilecek en büyük sıralı aday sayısı olsun. Uygun bölgenin dışında artık bütçe kalmadığı için
$$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c$$
alınır.
Uygun bir \((i,j)\) durumunda sıradaki tahmin bir pivot aday seçer. Bu pivot adayın kendisi tek başına bir ayırt edilebilir değerdir. Gizli değer \(a\)-maliyetli dala düşerse sonraki durum \((i+1,j)\), \(b\)-maliyetli dala düşerse sonraki durum \((i,j+1)\) olur.
Bu nedenle \((i,j)\) kökünden başlayan her strateji en fazla
$$1+D_c(i+1,j)+D_c(i,j+1)$$
aday ayırt edebilir.
Tersine bu üst sınır erişilebilirdir. Sol devam stratejisi \(L=D_c(i+1,j)\), sağ devam stratejisi \(R=D_c(i,j+1)\) aday ayırt edebiliyorsa, uzunluğu \(L+1+R\) olan sıralı bir blok tam olarak çözülebilir: \((L+1)\). aday tahmin edilir, soldaki blokta sol strateji, sağdaki blokta sağ strateji uygulanır.
Dolayısıyla rekürans yalnızca bir üst sınır değil, tam eşitliktir:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
Dış aramanın ihtiyaç duyduğu kapasite de
$$K(c,a,b)=D_c(0,0)$$
olur.
\(C(5,2,3)=5\) kontrol değeri mekanizmayı açık biçimde gösterir.
\(c=4\) için uygun durumlar \((0,0),(1,0),(2,0),(0,1)\)'dir. Ters yönde hesaplayınca
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4$$
elde edilir. Yani bütçe \(4\) iken ancak \(K(4,2,3)=4\) aday garanti edilebilir.
\(c=5\) için ek olarak \((1,1)\) durumu da uygun hâle gelir ve bu kez
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6$$
olur. Böylece \(K(5,2,3)=6\ge 5\). \(4\) yetmediği ve \(5\) yettiği için
$$C(5,2,3)=5$$
sonucuna ulaşılır.
Eğer \(c_1\le c_2\) ise \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\) olur. \(c_1\) bütçesinde kullanılabilen her durum \(c_2\) bütçesinde de kullanılabildiği için
$$K(c_1,a,b)\le K(c_2,a,b)$$
elde edilir. Bu monotonluk, \(C(n,a,b)\)'yi tam bir “cevap üzerinde binary search” problemine çevirir. Uygulama önce \(1,2,4,8,\dots\) şeklinde üst sınırı iki katına çıkarır; kapasite \(n\)'ye ulaşınca 90 biseksiyon adımı yapar.
\(F_1,\dots,F_{30}\) Fibonacci sayıları hesaplandıktan sonra
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30)$$
şeklindeki 30 parametre çifti kurulur. Her çift için \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\) hesaplanır ve tüm bu değerler toplanır. Yani matematiksel yük tamamen \(K(c,a,b)\) kapasite fonksiyonunun hızlı değerlendirilmesindedir.
Sabit bir \(c\) bütçesi için uygulama
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor$$
değerlerini alır, \((i_{\max}+2)\times(j_{\max}+2)\) boyutlu dikdörtgen bir DP tablosu kurar ve tabloyu sağ alttan sol üste doğru doldurur. Böylece bir hücre güncellenirken iki devam durumunun değeri zaten hesaplanmış olur.
\(a\) ve \(b\) irrasyonel kareköklerden geldiği için, \(ia+jb\le c+\varepsilon\) testinde \(\varepsilon=10^{-16}(1+c)\) toleransı kullanılır. Bu küçük pay, kayan nokta yuvarlama hatalarının sınırdaki hücreleri yanlış sınıflandırmasını engeller.
Ayrıca her DP değeri hedef \(n\)'de doyurulur. Bu, cevabı değiştirmez; çünkü dış arama yalnızca kapasitenin \(n\)'ye ulaşıp ulaşmadığını sorar. \(n\)'den büyük değerler bu karar açısından eşdeğerdir. Doyurma hem taşmayı önler hem de sayıları kontrol altında tutar.
C++, Python ve Java uygulamaları aynı şemayı izler: Fibonacci sayılarını üret, 30 bağımsız eşik aramasını çöz, sonunda toplamı sekiz ondalık basamakla yazdır.
\(K(c,a,b)\)'nin tek bir değerlendirilmesinde tablo boyutları
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1$$
olduğundan dinamik program \(O(IJ)\) zaman ve \(O(IJ)\) bellek kullanır.
\(C(n,a,b)\)'yi bulmak için üstel aralık genişletme \(O(\log C(n,a,b))\) adet kapasite hesabı gerektirir; ardından tam 90 biseksiyon hesabı gelir. Project Euler örneğinde yalnızca 30 parametre çifti bulunduğu için toplam çalışma süresi, \(k=1,\dots,30\) üzerindeki bu sabit yapılı aramaların toplamıdır.
Para costos reales positivos \(a\) y \(b\), sea \(C(n,a,b)\) el menor presupuesto \(c\) que garantiza el éxito en un juego de adivinación ordenado con al menos \(n\) candidatos: después de cada intento, una de las dos respuestas de desigualdad cuesta \(a\) y la otra cuesta \(b\). En el Problema 406 hay que calcular
$$\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}.$$
Explorar directamente todos los árboles de decisión es inviable, así que la solución transforma el juego en una programación dinámica sobre una retícula que cuenta cuántos candidatos ordenados puede soportar un presupuesto fijo.
Definamos \(K(c,a,b)\) como el mayor número de candidatos ordenados que siempre pueden distinguirse con costo total a lo sumo \(c\). Una vez conocida esa capacidad, el umbral buscado es
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$
Por tanto, la implementación resuelve dos tareas: calcular \(K(c,a,b)\) para un presupuesto fijo y luego buscar por bisección el menor \(c\) que hace que \(K(c,a,b)\) alcance el objetivo \(n\).
Supongamos que, en la ruta actual del árbol de decisión, ya han aparecido \(i\) respuestas del primer tipo y \(j\) del segundo tipo. El costo gastado hasta ese punto es
$$ia+jb.$$
Ese estado sigue siendo viable exactamente cuando
$$ia+jb\le c.$$
Así obtenemos la región finita de la retícula
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
Sea ahora \(D_c(i,j)\) el máximo número de candidatos ordenados que todavía pueden resolverse desde el estado \((i,j)\). Fuera de la región factible ya no queda presupuesto, así que
$$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c.$$
En un estado factible \((i,j)\), la siguiente jugada elige un candidato pivote. Ese pivote aporta por sí mismo un valor distinguible. Si el valor oculto cae en la rama de costo \(a\), el siguiente estado es \((i+1,j)\); si cae en la rama de costo \(b\), el siguiente estado es \((i,j+1)\).
Por ello, cualquier estrategia con raíz en \((i,j)\) puede distinguir a lo sumo
$$1+D_c(i+1,j)+D_c(i,j+1)$$
candidatos.
Además, esa cota es alcanzable. Si la continuación izquierda puede manejar \(L=D_c(i+1,j)\) candidatos y la derecha \(R=D_c(i,j+1)\), entonces un bloque ordenado de longitud \(L+1+R\) se resuelve exactamente: se adivina el candidato número \((L+1)\), se aplica la estrategia izquierda al bloque inferior y la derecha al superior.
Por tanto, la recurrencia es exacta:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
La capacidad que necesita la búsqueda exterior es entonces
$$K(c,a,b)=D_c(0,0).$$
El punto de control \(C(5,2,3)=5\) muestra bien el mecanismo.
Para \(c=4\), los estados factibles son \((0,0),(1,0),(2,0),(0,1)\). Calculando hacia atrás se obtiene
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
Así, un presupuesto de \(4\) solo garantiza \(K(4,2,3)=4\) candidatos.
Para \(c=5\) aparece además el estado \((1,1)\), y ahora
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
Por tanto \(K(5,2,3)=6\ge 5\). Como \(4\) no basta y \(5\) sí, concluimos que
$$C(5,2,3)=5.$$
Si \(c_1\le c_2\), entonces \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). Todo estado disponible con presupuesto \(c_1\) también lo está con \(c_2\), de modo que
$$K(c_1,a,b)\le K(c_2,a,b).$$
Esa monotonía convierte a \(C(n,a,b)\) en un problema clásico de “búsqueda binaria sobre la respuesta”. La implementación primero duplica una cota superior \(1,2,4,8,\dots\) hasta que la capacidad alcance \(n\), y después ejecuta 90 pasos de bisección.
Una vez calculados los números de Fibonacci \(F_1,\dots,F_{30}\), el algoritmo forma los 30 pares
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
Para cada par se calcula \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\) y luego se suman los 30 resultados. Por eso todo el trabajo matemático está concentrado en evaluar eficientemente la función de capacidad \(K(c,a,b)\).
Para un presupuesto fijo \(c\), la implementación define
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
reserva una tabla DP rectangular de tamaño \((i_{\max}+2)\times(j_{\max}+2)\) y la rellena desde la esquina inferior derecha hacia la superior izquierda, de forma que los dos estados sucesores ya estén calculados cuando se actualiza una celda.
En la prueba de factibilidad \(ia+jb\le c+\varepsilon\) se usa una tolerancia diminuta \(\varepsilon=10^{-16}(1+c)\) para absorber errores de redondeo, ya que \(a\) y \(b\) son raíces cuadradas irracionales.
Cada valor DP también se satura en el objetivo \(n\). Eso no altera la respuesta porque la búsqueda exterior solo pregunta si la capacidad ya alcanzó \(n\); cualquier valor mayor es equivalente para esa decisión. La saturación evita desbordamientos y mantiene controlado el rango numérico.
Las implementaciones en C++, Python y Java siguen exactamente este plan: generar Fibonacci, resolver 30 búsquedas de umbral independientes e imprimir la suma final con ocho decimales.
En una sola evaluación de \(K(c,a,b)\), las dimensiones de la tabla son
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
por lo que la programación dinámica usa \(O(IJ)\) tiempo y \(O(IJ)\) memoria.
Para obtener \(C(n,a,b)\), el acotamiento exponencial requiere \(O(\log C(n,a,b))\) evaluaciones de capacidad y luego vienen exactamente 90 evaluaciones de bisección. Como la instancia de Project Euler tiene solo 30 pares de parámetros, el tiempo total es la suma de esos costos fijos de búsqueda para \(k=1,\dots,30\).
对正实数代价 \(a,b\)，记 \(C(n,a,b)\) 为这样一个最小预算 \(c\)：在一个有序猜数游戏中，面对至少 \(n\) 个候选值时，总能保证成功；每次猜测之后，两种“不相等”分支分别额外消耗 \(a\) 和 \(b\)。第 406 题要求计算
$$\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}.$$
如果直接枚举所有决策树，规模完全不可接受。因此解法先回答一个更基础的问题：给定预算 \(c\)，最多能区分多少个有序候选值。
定义 \(K(c,a,b)\) 为总成本不超过 \(c\) 时，保证可以区分的最大有序候选数。只要知道这个容量函数，就有
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$
所以实现实际上分成两层：内层在固定预算下计算 \(K(c,a,b)\)，外层再二分最小的可行预算 \(c\)。
设当前决策路径上，已经出现了 \(i\) 次第一类回答、\(j\) 次第二类回答，那么已花费成本就是
$$ia+jb.$$
该状态仍然可用，当且仅当
$$ia+jb\le c.$$
于是得到有限的可行格点区域
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
再定义 \(D_c(i,j)\) 为从状态 \((i,j)\) 出发，仍然能够保证区分的最大有序候选数。若 \((i,j)\) 不在可行区域内，说明预算已经耗尽，因此
$$D_c(i,j)=0\qquad\text{当 }(i,j)\notin \mathcal{R}_c.$$
在一个可行状态 \((i,j)\) 上，下一次猜测会选定一个枢轴候选。这个枢轴本身贡献 1 个可区分值。若真实值落入 \(a\)-代价分支，下一状态是 \((i+1,j)\)；若落入 \(b\)-代价分支，下一状态是 \((i,j+1)\)。
因此，以 \((i,j)\) 为根的任意策略至多能区分
$$1+D_c(i+1,j)+D_c(i,j+1)$$
个候选值。
反过来，这个上界又是可以达到的。若左侧后续最多处理 \(L=D_c(i+1,j)\) 个候选，右侧后续最多处理 \(R=D_c(i,j+1)\) 个候选，那么长度为 \(L+1+R\) 的有序区间可以被恰好处理：把第 \((L+1)\) 个元素作为当前猜测，左边区间交给左策略，右边区间交给右策略。
于是递推式是严格成立的：
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
我们真正需要的容量函数就是
$$K(c,a,b)=D_c(0,0).$$
代码中的检查点 \(C(5,2,3)=5\) 很适合作为示例。
当 \(c=4\) 时，可行状态只有 \((0,0),(1,0),(2,0),(0,1)\)。倒推得到
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
所以预算 \(4\) 只能保证 \(K(4,2,3)=4\) 个候选。
当 \(c=5\) 时，新增可行状态 \((1,1)\)，此时
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
因此 \(K(5,2,3)=6\ge 5\)。因为 \(4\) 不够而 \(5\) 足够，所以
$$C(5,2,3)=5.$$
若 \(c_1\le c_2\)，则 \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\)。预算较小可用的所有状态，在预算较大时仍然可用，因此
$$K(c_1,a,b)\le K(c_2,a,b).$$
这种单调性使得 \(C(n,a,b)\) 可以用“对答案二分”来求。实现先用 \(1,2,4,8,\dots\) 这样的指数扩张找到足够大的上界，再进行 90 次二分逼近。
先计算 \(F_1,\dots,F_{30}\)，再构造 30 组参数
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
对每一组参数，求出 \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\)，最后把这 30 个结果相加。因此数学核心完全落在如何高效评估容量函数 \(K(c,a,b)\) 上。
对固定预算 \(c\)，实现先取
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
然后分配一个 \((i_{\max}+2)\times(j_{\max}+2)\) 的 DP 表，并从右下向左上填表，这样更新某个单元时，它依赖的两个后继状态都已经算好。
由于 \(a,b\) 来自无理数平方根，可行性测试写成 \(ia+jb\le c+\varepsilon\)，其中 \(\varepsilon=10^{-16}(1+c)\)。这个很小的容差用来吸收浮点舍入误差，避免边界点被误判。
每个 DP 值还会被截断到目标 \(n\)。这不会改变最终答案，因为外层搜索只关心容量是否已经达到 \(n\)；一旦达到，再大的值在判定上完全等价。这样的饱和处理既防止溢出，也让数值范围保持稳定。
C++、Python 和 Java 三份实现都遵循同一结构：生成 Fibonacci 数，分别求 30 个阈值，再把总和按 8 位小数输出。
单次计算 \(K(c,a,b)\) 时，表的边长为
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
因此动态规划的时间和空间复杂度都是 \(O(IJ)\)。
为了得到 \(C(n,a,b)\)，指数扩张阶段需要 \(O(\log C(n,a,b))\) 次容量评估，随后固定再做 90 次二分评估。由于题目只包含 30 组参数，整体运行时间就是这 30 次固定结构搜索的总和。
Для положительных вещественных стоимостей \(a\) и \(b\) обозначим через \(C(n,a,b)\) минимальный бюджет \(c\), который гарантирует успех в упорядоченной игре угадывания с не менее чем \(n\) кандидатами: после каждой попытки одна из двух неравных ветвей стоит \(a\), а другая \(b\). В задаче 406 требуется вычислить
$$\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}.$$
Перебор всех возможных стратегий невозможен, поэтому решение сначала отвечает на вопрос: сколько упорядоченных кандидатов вообще можно гарантированно различить при фиксированном бюджете \(c\).
Определим \(K(c,a,b)\) как максимальное число упорядоченных кандидатов, которые можно всегда различить при суммарной стоимости не более \(c\). Тогда искомый порог выражается как
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$
Значит, программа решает две задачи: для фиксированного бюджета вычисляет \(K(c,a,b)\), а затем двоичным поиском находит наименьшее \(c\), при котором \(K(c,a,b)\) достигает цели \(n\).
Пусть на текущем пути дерева решений уже встретилось \(i\) ответов первого типа и \(j\) ответов второго типа. Тогда уже потраченная стоимость равна
$$ia+jb.$$
Состояние остается допустимым тогда и только тогда, когда
$$ia+jb\le c.$$
Это задает конечную допустимую область решетки
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
Обозначим через \(D_c(i,j)\) максимальное число упорядоченных кандидатов, которые еще можно гарантированно различить из состояния \((i,j)\). Вне допустимой области бюджета уже не осталось, поэтому
$$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c.$$
В допустимом состоянии \((i,j)\) следующий ход выбирает опорного кандидата. Сам этот опорный элемент дает один различимый вариант. Если скрытое значение уходит в ветвь со стоимостью \(a\), следующее состояние равно \((i+1,j)\); если в ветвь со стоимостью \(b\), то \((i,j+1)\).
Следовательно, любая стратегия с корнем в \((i,j)\) может различить не более
$$1+D_c(i+1,j)+D_c(i,j+1)$$
кандидатов.
Обратная оценка также достижима. Если левая подстратегия обрабатывает \(L=D_c(i+1,j)\) кандидатов, а правая \(R=D_c(i,j+1)\), то можно точно обработать упорядоченный блок длины \(L+1+R\): угадать \((L+1)\)-й элемент, левый блок передать левой стратегии, правый блок правой.
Тем самым рекурсия является точным равенством:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
Нужная внешнему поиску емкость равна
$$K(c,a,b)=D_c(0,0).$$
Контрольное значение \(C(5,2,3)=5\) хорошо показывает механику.
При \(c=4\) допустимы состояния \((0,0),(1,0),(2,0),(0,1)\). Обратный проход дает
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
Значит, бюджета \(4\) хватает лишь на \(K(4,2,3)=4\) кандидатов.
При \(c=5\) появляется дополнительное состояние \((1,1)\), и теперь
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
Следовательно, \(K(5,2,3)=6\ge 5\). Поскольку \(4\) недостаточно, а \(5\) достаточно, получаем
$$C(5,2,3)=5.$$
Если \(c_1\le c_2\), то \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). Любое состояние, допустимое при бюджете \(c_1\), допустимо и при \(c_2\), поэтому
$$K(c_1,a,b)\le K(c_2,a,b).$$
Именно эта монотонность превращает задачу нахождения \(C(n,a,b)\) в стандартный двоичный поиск по ответу. Реализация сначала удваивает верхнюю границу \(1,2,4,8,\dots\), пока емкость не станет не меньше \(n\), а затем выполняет 90 шагов бисекции.
После вычисления чисел Фибоначчи \(F_1,\dots,F_{30}\) формируются 30 пар параметров
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
Для каждой пары вычисляется \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\), после чего все 30 значений суммируются. Таким образом, вся математическая сложность сосредоточена в эффективном вычислении функции емкости \(K(c,a,b)\).
Для фиксированного бюджета \(c\) реализация задает
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
выделяет прямоугольную DP-таблицу размера \((i_{\max}+2)\times(j_{\max}+2)\) и заполняет ее от правого нижнего угла к левому верхнему, чтобы оба последующих состояния уже были посчитаны в момент обновления текущей ячейки.
В проверке допустимости \(ia+jb\le c+\varepsilon\) используется очень маленький допуск \(\varepsilon=10^{-16}(1+c)\). Он нужен из-за округлений с плавающей точкой, поскольку \(a\) и \(b\) являются иррациональными квадратными корнями.
Кроме того, каждое значение DP насыщается сверху целевым \(n\). Это не меняет ответ, потому что внешний поиск интересуется только вопросом, достигла ли емкость значения \(n\). Все большие числа для этой проверки эквивалентны. Насыщение защищает от переполнения и удерживает диапазон значений под контролем.
Реализации на C++, Python и Java используют один и тот же план: строят числа Фибоначчи, решают 30 независимых поисков порога и печатают итоговую сумму с восемью знаками после запятой.
Для одного вычисления \(K(c,a,b)\) размеры таблицы равны
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
поэтому динамическое программирование требует \(O(IJ)\) времени и \(O(IJ)\) памяти.
Чтобы получить \(C(n,a,b)\), этап экспоненциального расширения использует \(O(\log C(n,a,b))\) вычислений емкости, после чего выполняются ровно 90 бисекционных вычислений. Так как в задаче Project Euler рассматриваются только 30 пар параметров, общее время равно сумме этих фиксированных поисков по всем \(k=1,\dots,30\).
للتكلفتين الحقيقيتين الموجبتين \(a\) و\(b\)، نرمز بـ \(C(n,a,b)\) إلى أصغر ميزانية \(c\) تضمن النجاح في لعبة تخمين مرتبة تحتوي على ما لا يقل عن \(n\) مرشحًا: بعد كل تخمين، إحدى إجابتي عدم المساواة تكلف \(a\) والأخرى تكلف \(b\). المطلوب في المسألة 406 هو حساب
$$\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}.$$
من المستحيل عمليًا استعراض كل أشجار القرار الممكنة، لذلك تحوّل الحل المسألة إلى برمجة ديناميكية على شبكة تعدّ عدد القيم المرتبة التي يمكن لميزانية ثابتة أن تميّزها.
لنعرّف \(K(c,a,b)\) بأنه أكبر عدد من المرشحين المرتبين يمكن تمييزهم دائمًا عندما لا تتجاوز الكلفة الكلية \(c\). عند معرفة هذه الدالة تصبح العتبة المطلوبة
$$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$$
وبالتالي فالتنفيذ يحل مسألتين: أولًا حساب \(K(c,a,b)\) عند ميزانية ثابتة، ثم البحث الثنائي عن أصغر \(c\) يحقق \(K(c,a,b)\ge n\).
افترض أنه على المسار الحالي في شجرة القرار ظهرت \(i\) إجابات من النوع الأول و\(j\) إجابات من النوع الثاني. عندئذ تكون الكلفة المصروفة حتى تلك اللحظة
$$ia+jb.$$
وتبقى الحالة صالحة إذا وفقط إذا كان
$$ia+jb\le c.$$
وهذا يعطي منطقة الشبكة المنتهية
$$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$$
ولنعرّف \(D_c(i,j)\) بأنه أكبر عدد من المرشحين المرتبين الذين ما زال يمكن حسمهم انطلاقًا من الحالة \((i,j)\). خارج المنطقة الصالحة لا تبقى أي ميزانية، لذلك
$$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c.$$
في الحالة الصالحة \((i,j)\)، يختار التخمين التالي مرشحًا محوريًا. هذا المرشح نفسه يعطي قيمة مميزة واحدة. إذا وقع العدد المخفي في الفرع ذي الكلفة \(a\)، تصبح الحالة التالية \((i+1,j)\)، وإذا وقع في الفرع ذي الكلفة \(b\)، تصبح الحالة التالية \((i,j+1)\).
إذًا فإن أي استراتيجية جذورها عند \((i,j)\) لا تستطيع أن تميّز أكثر من
$$1+D_c(i+1,j)+D_c(i,j+1)$$
مرشحًا.
وفي المقابل يمكن بلوغ هذا الحد فعلًا. فإذا كانت الاستراتيجية اليسرى تستطيع معالجة \(L=D_c(i+1,j)\) مرشحًا، واليمنى تستطيع معالجة \(R=D_c(i,j+1)\) مرشحًا، فيمكن معالجة مقطع مرتب طوله \(L+1+R\) تمامًا: نخمّن المرشح رقم \((L+1)\)، ثم نستخدم الاستراتيجية اليسرى للمقطع الأدنى واليمنى للمقطع الأعلى.
ومن ثم فالعلاقة التالية صحيحة على وجه الدقة:
$$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$$
والسعة التي تحتاجها عملية البحث الخارجية هي ببساطة
$$K(c,a,b)=D_c(0,0).$$
القيمة الاختبارية \(C(5,2,3)=5\) توضح الفكرة جيدًا.
عندما يكون \(c=4\)، تكون الحالات الصالحة هي \((0,0),(1,0),(2,0),(0,1)\). وبالحساب العكسي نحصل على
$$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$$
إذن الميزانية \(4\) تضمن فقط \(K(4,2,3)=4\) مرشحين.
أما عند \(c=5\) فتظهر الحالة الإضافية \((1,1)\)، ويصبح لدينا
$$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$$
وعليه فإن \(K(5,2,3)=6\ge 5\). وبما أن \(4\) غير كافية و\(5\) كافية، نستنتج أن
$$C(5,2,3)=5.$$
إذا كان \(c_1\le c_2\)، فإن \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). كل حالة متاحة تحت الميزانية \(c_1\) تبقى متاحة تحت الميزانية \(c_2\)، لذا
$$K(c_1,a,b)\le K(c_2,a,b).$$
هذه الرتابة تجعل \(C(n,a,b)\) مسألة قياسية من نوع “البحث الثنائي على الجواب”. يبدأ التنفيذ بتوسيع حد علوي على الصورة \(1,2,4,8,\dots\) حتى تصل السعة إلى \(n\)، ثم يجري 90 خطوة من التنصيف.
بعد حساب أعداد فيبوناتشي \(F_1,\dots,F_{30}\)، تُبنى الأزواج الثلاثون
$$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$$
ثم يُحسب لكل زوج الحد \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\)، وتُجمع القيم الثلاثون كلها. لذلك يتركز العبء الرياضي بالكامل في تقييم دالة السعة \(K(c,a,b)\) بكفاءة.
عند ميزانية ثابتة \(c\)، يحدد التنفيذ
$$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$$
ثم ينشئ جدول DP مستطيلاً حجمه \((i_{\max}+2)\times(j_{\max}+2)\)، ويملؤه من أسفل اليمين إلى أعلى اليسار بحيث تكون حالتا الاستمرار قد حُسبتا مسبقًا عند تحديث أي خلية.
في اختبار الصلاحية \(ia+jb\le c+\varepsilon\) تُضاف سماحية صغيرة جدًا \(\varepsilon=10^{-16}(1+c)\)، وذلك لحماية الحدود من أخطاء التقريب العائم لأن \(a\) و\(b\) جذور تربيعية غير نسبية.
كما تُقصّ كل قيمة DP عند الهدف \(n\). وهذا لا يغير الجواب لأن البحث الخارجي لا يسأل إلا: هل بلغت السعة \(n\) أم لا؟ وما بعد ذلك غير مهم لاتخاذ القرار. هذا الإشباع يمنع الفيض ويحافظ على الاستقرار العددي.
وتتبع تطبيقات C++ وPython وJava الخطة نفسها: توليد أعداد فيبوناتشي، حل 30 عملية بحث مستقلة عن العتبة، ثم طباعة المجموع النهائي حتى 8 منازل عشرية.
في تقييم واحد للدالة \(K(c,a,b)\)، تكون أبعاد الجدول
$$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$$
ولذلك تستخدم البرمجة الديناميكية زمنًا \(O(IJ)\) وذاكرة \(O(IJ)\).
ولإيجاد \(C(n,a,b)\)، يحتاج التوسيع الأسي للحدود إلى \(O(\log C(n,a,b))\) من تقييمات السعة، ثم تأتي 90 تقييمات تنصيف ثابتة. وبما أن مسألة Project Euler تحتوي فقط على 30 زوجًا من المعاملات، فإن الزمن الكلي هو مجموع هذه العمليات الثابتة على جميع القيم \(k=1,\dots,30\).