Project Euler 240 asks for the number of ordered outcomes obtained by rolling 20 twelve-sided dice such that, after sorting the 20 results in descending order, the 10 largest values add up to 70. If the sorted roll is \(x_1 \ge x_2 \ge \cdots \ge x_{20}\), the condition is
$$x_1+x_2+\cdots+x_{10}=70.$$
The dice are distinguishable before sorting, so two rolls with the same multiset of face values still count as different outcomes when those values are assigned to different dice. Any correct method therefore has to count raw rolls, not just sorted patterns.
The implementations solve the problem by scanning face values from 12 down to 1. At each step they decide how many remaining dice show the current face, keep track of how many positions of the top ten have already been forced by larger faces, and accumulate the partial top-ten sum.
Let \(c_v\) be the number of dice showing face \(v\), for \(1 \le v \le 12\). Then
$$\sum_{v=1}^{12} c_v = 20.$$
Once the counts \(c_{12},c_{11},\dots,c_1\) are known, the sorted roll is determined: first come all 12s, then all 11s, and so on. The only subtlety is that not every die contributes to the top-ten sum. If we define \(t_v\) as the number of face-\(v\) dice that actually land in the top ten, then scanning downward gives the deterministic rule
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
The constraint in the problem is therefore equivalent to
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
This is the key invariant behind the dynamic program: when higher faces have already been fixed, the current face can fill only the top-ten slots that are still vacant.
For \(v=12,11,\dots,1\), let \(D_v(r,m,s)\) denote the number of partial assignments after all faces strictly larger than \(v\) have already been processed, where:
\(r\) is the number of dice whose values have not yet been assigned, \(m\) is the number of positions among the 10 largest dice that are already forced by the larger faces, and \(s\) is the sum contributed by those already forced top-ten entries.
Before any face has been processed, every die is still free and nothing has entered the top ten, so the initial state is
$$D_{12}(20,0,0)=1.$$
All other initial states are zero.
Suppose we are processing face \(v\) from a state \((r,m,s)\). Choose \(c\) of the \(r\) remaining dice to show value \(v\). There are
$$\binom{r}{c}$$
ways to choose which labeled dice receive that value.
Among those \(c\) dice, only
$$a=\min(c,10-m)$$
can still belong to the top ten, because exactly \(10-m\) top-ten positions remain unfilled and every later face is smaller than \(v\). Therefore the recurrence is
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
provided that \(s+a\,v \le 70\). Once \(m=10\), the top ten are already completely determined, so all lower faces affect only the bottom ten dice and leave the sum unchanged.
If a complete roll has multiplicities \(c_{12},c_{11},\dots,c_1\), then the descending-face sweep contributes the product
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
This telescopes to
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
which is exactly the multinomial count of how many ordered raw rolls realize that multiset of faces. So the dynamic program is not merely counting sorted histograms; it is counting the actual dice outcomes required by the problem.
The sample configuration in the statement uses 5 six-sided dice and asks for the number of rolls whose largest 3 dice sum to 15; that total is 1111. One local transition explains the recurrence clearly.
Assume faces 6 and 5 have already contributed one die each. Then the state is \((r,m,s)=(3,2,11)\): three dice remain unassigned, two of the top three places are fixed, and their partial sum is 11. If we now assign \(c=2\) dice to face 4, then
$$a=\min(2,3-2)=1.$$
Only one of those two 4s can still enter the top three, because only one slot is open. The transition factor is \(\binom{3}{2}=3\), and the new state becomes \((1,3,15)\). If the last die later receives value 1, the completed multiset is \((6,5,4,4,1)\), whose number of ordered realizations is
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}.$$
This is exactly the number of raw rolls with that multiset, and only one of the two 4s contributes to the top-three sum.
After face 1 has been processed, a valid complete roll must have no unassigned dice left, all 10 top positions determined, and top-ten sum 70. Therefore the final answer is
$$D_0(0,10,70).$$
No other terminal state can represent a complete solution to the original problem.
The C++, Python, and Java implementations first build Pascal's triangle up to row 20. That provides every binomial coefficient \(\binom{r}{c}\) needed by the recurrence, and it also keeps the main loop free of repeated combinatorial recomputation.
The implementation stores a three-dimensional table indexed by remaining dice, filled top-ten positions, and current top-ten sum. For each face value from 12 down to 1, it creates the next layer, scans every reachable state, and tries every possible number of dice assigned to that face from 0 up to the number still unassigned.
The update uses exactly the recurrence above: compute how many of the newly assigned dice still enter the top ten, update the filled-count and partial sum, multiply by the correct binomial factor, and accumulate into the next layer. States with zero count are skipped immediately.
After the sweep finishes, the desired count is the entry with 0 dice remaining, 10 top slots filled, and sum 70. The C++ implementation also includes two sanity checks before solving the main instance: it verifies the published sample value 1111 for \((5,6,3,15)\), and it compares one smaller case against a brute-force enumeration. The Python and Java implementations apply the same dynamic program directly to the target parameters.
For general parameters \((N,F,K,S)\), the state space has size \((N+1)(K+1)(S+1)\). For each of the \(F\) face values, each state tries all \(c=0,1,\dots,r\), so the worst-case running time is
$$O(F\,N^2KS).$$
Using separate current and next layers keeps the memory usage at
$$O(NKS).$$
For the actual instance \(N=20\), \(F=12\), \(K=10\), \(S=70\), each layer contains only \(21 \cdot 11 \cdot 71 = 16401\) states, so the method is easily fast enough.
Bei Project Euler 240 sollen 20 zwölfseitige Würfel geworfen werden. Sortiert man die 20 Ergebnisse absteigend, dann müssen die 10 größten Werte zusammen genau 70 ergeben. Für den sortierten Wurf \(x_1 \ge x_2 \ge \cdots \ge x_{20}\) lautet die Bedingung also
$$x_1+x_2+\cdots+x_{10}=70.$$
Gezählt werden geordnete Rohwürfe. Die Würfel sind vor dem Sortieren unterscheidbar, daher zählen zwei Würfe mit demselben Multiset von Augenzahlen als verschiedene Ergebnisse, wenn diese Zahlen auf unterschiedliche Würfel verteilt sind.
Die Implementierungen durchlaufen die Augenzahlen von 12 hinunter bis 1. Für jeden Wert wird festgelegt, wie viele der noch freien Würfel diese Augenzahl erhalten, wie viele Plätze unter den größten 10 Würfeln dadurch bereits definitiv besetzt sind und wie groß ihre bisherige Summe ist.
Sei \(c_v\) die Anzahl der Würfel mit Wert \(v\), für \(1 \le v \le 12\). Dann gilt
$$\sum_{v=1}^{12} c_v = 20.$$
Sind die Werte \(c_{12},c_{11},\dots,c_1\) bekannt, ist der sortierte Wurf vollständig bestimmt: zuerst alle 12er, dann alle 11er und so weiter. Nicht jede dieser Augenzahlen trägt jedoch zur Summe der größten 10 bei. Definiert man \(t_v\) als die Anzahl der \(v\)-Würfel, die tatsächlich in den Top 10 landen, dann ergibt die absteigende Betrachtung die Regel
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
Damit ist die Bedingung des Problems gleichbedeutend mit
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
Genau daraus entsteht die zentrale Invariante der dynamischen Programmierung: Wenn alle größeren Augenzahlen schon feststehen, kann der aktuelle Wert nur noch die verbleibenden freien Plätze unter den größten 10 auffüllen.
Für \(v=12,11,\dots,1\) bezeichne \(D_v(r,m,s)\) die Anzahl partieller Belegungen, nachdem alle Werte strikt größer als \(v\) bereits verarbeitet wurden. Dabei bedeutet:
\(r\) noch nicht zugewiesene Würfel, \(m\) bereits festgelegte Positionen innerhalb der größten 10 Würfel und \(s\) die Summe dieser bereits festgelegten Top-10-Einträge.
Zu Beginn ist noch kein Wert verarbeitet, also
$$D_{12}(20,0,0)=1,$$
während alle anderen Anfangszustände null sind.
Verarbeite nun den Wert \(v\) aus einem Zustand \((r,m,s)\). Wähle \(c\) der \(r\) verbleibenden Würfel aus, die den Wert \(v\) erhalten. Dafür gibt es
$$\binom{r}{c}$$
Möglichkeiten.
Von diesen \(c\) Würfeln können nur
$$a=\min(c,10-m)$$
noch zu den größten 10 gehören, denn es sind nur \(10-m\) Plätze frei und alle später verarbeiteten Werte sind kleiner als \(v\). Daher lautet die Rekurrenz
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
sofern \(s+a\,v \le 70\) gilt. Sobald \(m=10\) erreicht ist, ist die Top-10-Menge vollständig bestimmt, und kleinere Werte beeinflussen nur noch die unteren 10 Würfel.
Hat ein vollständiger Wurf die Vielfachheiten \(c_{12},c_{11},\dots,c_1\), dann liefert der Durchlauf von oben nach unten das Produkt
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
Dieses Produkt vereinfacht sich zu
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
also genau zum Multinomialkoeffizienten der geordneten Rohwürfe mit diesem Multiset. Die DP zählt also nicht nur Histogramme, sondern exakt die gesuchten Würfelergebnisse.
Im veröffentlichten Beispiel werden 5 sechsseitige Würfel geworfen, und die größten 3 sollen zusammen 15 ergeben; die Gesamtzahl ist dort 1111. Ein einzelner Übergang zeigt die Logik der Rekurrenz besonders deutlich.
Angenommen, die Werte 6 und 5 haben bereits jeweils einen Würfel geliefert. Dann befindet man sich im Zustand \((r,m,s)=(3,2,11)\): Drei Würfel sind noch frei, zwei der Top-3-Plätze stehen fest, ihre Teilsumme ist 11. Weist man nun \(c=2\) Würfeln den Wert 4 zu, so ist
$$a=\min(2,3-2)=1.$$
Nur eine dieser beiden 4en kann noch in die größten 3 eingehen, weil nur noch ein Platz frei ist. Der Übergang bekommt den Faktor \(\binom{3}{2}=3\) und führt zum Zustand \((1,3,15)\). Erhält der letzte Würfel später den Wert 1, entsteht das Multiset \((6,5,4,4,1)\) mit
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}$$
geordneten Realisierungen. Genau eine der beiden 4en trägt dabei zur Summe der größten 3 bei.
Nach der Verarbeitung des Wertes 1 ist ein vollständiger gültiger Wurf genau dann erreicht, wenn kein Würfel mehr unvergeben ist, alle 10 Top-Plätze feststehen und ihre Summe 70 beträgt. Die gesuchte Antwort ist also
$$D_0(0,10,70).$$
Die C++-, Python- und Java-Implementierungen erzeugen zunächst Pascalsches Dreieck bis Zeile 20. Damit stehen alle benötigten Werte \(\binom{r}{c}\) sofort zur Verfügung, und die eigentliche DP muss keine Kombinationen mehr neu berechnen.
Gespeichert wird eine dreidimensionale Tabelle mit den Achsen verbleibende Würfel, bereits gefüllte Top-10-Plätze und aktuelle Top-10-Summe. Für jeden Wert von 12 bis 1 wird eine neue Schicht aufgebaut. Alle erreichbaren Zustände werden durchlaufen, Nullzustände sofort übersprungen und für jeden Zustand alle Möglichkeiten \(c=0,1,\dots,r\) ausprobiert.
Jedes Update setzt exakt die Rekurrenz um: Wie viele der neu vergebenen Würfel noch in die Top 10 fallen, wie sich dadurch die Füllzahl und die Zwischensumme ändern und mit welchem Binomialfaktor der Beitrag gewichtet wird.
Nach der letzten Schicht ist der gesuchte Wert der Eintrag mit 0 verbleibenden Würfeln, 10 gefüllten Top-Plätzen und Summe 70. Die C++-Version enthält zusätzlich zwei Plausibilitätsprüfungen: den veröffentlichten Beispielwert 1111 für \((5,6,3,15)\) und einen weiteren kleinen Vergleich mit vollständiger Brute-Force-Zählung. Die Python- und Java-Versionen werten dieselbe DP direkt für den Zielparameter \((20,12,10,70)\) aus.
Für allgemeine Parameter \((N,F,K,S)\) besitzt der Zustandsraum die Größe \((N+1)(K+1)(S+1)\). Für jeden der \(F\) Werte werden pro Zustand bis zu \(N+1\) Möglichkeiten für \(c\) betrachtet. Daraus ergibt sich im Worst Case
$$O(F\,N^2KS)$$
Zeitaufwand.
Da nur eine aktuelle und eine nächste Schicht gespeichert werden, beträgt der Speicherverbrauch
$$O(NKS).$$
Für die konkrete Aufgabe mit \(N=20\), \(F=12\), \(K=10\), \(S=70\) enthält jede Schicht nur \(21 \cdot 11 \cdot 71 = 16401\) Zustände und ist damit sehr klein.
Project Euler 240, 20 adet 12 yüzlü zar atıldığında sonuçların büyükten küçüğe sıralanmış hâlindeki en büyük 10 değerin toplamının tam olarak 70 olduğu kaç farklı sıralı ham atış bulunduğunu sorar. Sıralanmış sonuçlar \(x_1 \ge x_2 \ge \cdots \ge x_{20}\) ise koşul
$$x_1+x_2+\cdots+x_{10}=70$$
şeklindedir. Burada zarlar sıralamadan önce ayırt edilebilir kabul edildiği için, aynı yüz çokluğuna sahip iki sonuç farklı zarlara dağıtıldıklarında farklı ham atışlar olarak sayılır.
Uygulamalar çözümü 12'den 1'e doğru yüz değerlerini tarayarak kurar. Her adımda henüz atanmamış zarlardan kaç tanesinin mevcut yüzü göstereceği seçilir; aynı anda en büyük 10 konumdan kaçının daha büyük yüzler tarafından kesinleştiği ve o ana kadar bu 10'lu toplamın kaç olduğu tutulur.
\(1 \le v \le 12\) için \(c_v\), değeri \(v\) olan zar sayısı olsun. O zaman
$$\sum_{v=1}^{12} c_v = 20.$$
\(c_{12},c_{11},\dots,c_1\) biliniyorsa sıralanmış dizi tamamen bellidir: önce tüm 12'ler, sonra 11'ler, sonra 10'lar gelir. Fakat bunların hepsi en büyük 10 toplamına girmez. Eğer \(t_v\), gerçekten ilk 10'a giren \(v\) değerli zarların sayısıysa, yukarıdan aşağıya tarama şu deterministik kuralı verir:
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
Dolayısıyla problem koşulu şu iki eşitliğe denktir:
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
Dinamik programın temel değişmezi budur: daha büyük yüzler yerleştirildikten sonra, mevcut yüz yalnızca hâlâ boş olan ilk 10 yuvasını doldurabilir.
\(v=12,11,\dots,1\) için \(D_v(r,m,s)\) şu sayıyı göstersin: \(v\)'den büyük tüm yüzler zaten işlendiğinde, \(r\) tane atanmamış zar kalmış, en büyük 10 içindeki \(m\) konum daha büyük yüzler tarafından kesinleşmiş ve bu kesinleşmiş girişlerin toplamı \(s\) olmuş olsun.
Başlangıçta hiçbir yüz işlenmemiştir; bu yüzden tek dolu başlangıç durumu
$$D_{12}(20,0,0)=1$$
olur.
Şimdi \((r,m,s)\) durumundayken yüz değeri \(v\)'yi işleyelim. Kalan \(r\) zar içinden \(c\) tanesinin \(v\) gelmesini seçelim. Bunu yapmanın sayısı
$$\binom{r}{c}$$
kadardır.
Bu \(c\) zarın sadece
$$a=\min(c,10-m)$$
kadarı en büyük 10'a girebilir; çünkü yalnızca \(10-m\) yuva boş kalmıştır ve bundan sonra işlenecek tüm yüzler \(v\)'den küçüktür. Dolayısıyla yineleme
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c}$$
şeklindedir; tabii \(s+a\,v \le 70\) olmalıdır. \(m=10\) olduğunda ilk 10 tamamen belirlenmiştir; daha küçük yüzler artık sadece alttaki 10 zarı etkiler.
Tam bir sonucun yüz çoklukları \(c_{12},c_{11},\dots,c_1\) olsun. Yüzleri büyükten küçüğe işlerken oluşan çarpım
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}$$
olur. Bu çarpım sadeleşince
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!}$$
elde edilir; bu da aynı yüz çokluğunu veren sıralı ham atışların tam multinom sayısıdır. Yani yöntem yalnızca sıralanmış kalıpları değil, problemin istediği gerçek zar dizilerini sayar.
Problem metnindeki küçük örnek 5 adet 6 yüzlü zar için, en büyük 3 zarın toplamı 15 olduğunda toplam 1111 sonuç bulunduğunu söyler. Tek bir geçiş bile yöntemin mantığını açıkça gösterir.
Diyelim ki 6 ve 5 değerleri şimdiden birer kez yerleşti. O zaman durum \((r,m,s)=(3,2,11)\) olur: üç zar henüz atanmadı, ilk 3'ün iki yeri doldu ve kısmi toplam 11. Şimdi \(c=2\) zarın 4 gelmesine karar verirsek
$$a=\min(2,3-2)=1$$
olur. Bu iki tane 4'ten yalnızca biri ilk 3'e girebilir; çünkü tek boş yer kalmıştır. Geçiş katsayısı \(\binom{3}{2}=3\) olur ve yeni durum \((1,3,15)\)'tir. Son kalan zar daha sonra 1 olursa ortaya çıkan çokluk \((6,5,4,4,1)\) olur ve bunun sıralı gerçekleşme sayısı
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}$$
eder. Görüldüğü gibi iki tane 4 vardır, ama yalnızca biri en büyük 3 toplamına katkı yapar.
Yüz değeri 1 de işlendiğinde geçerli bir tam atış için artık atanmamış zar kalmamalı, ilk 10'un tamamı belirlenmiş olmalı ve toplam 70 çıkmalıdır. Bu yüzden aranan sonuç
$$D_0(0,10,70)$$
değeridir.
C++, Python ve Java uygulamaları önce 20. satıra kadar Pascal üçgenini üretir. Böylece tüm \(\binom{r}{c}\) değerleri hazır olur ve ana döngü sırasında aynı kombinasyonlar tekrar tekrar hesaplanmaz.
Uygulama, eksenleri kalan zar sayısı, dolmuş ilk-10 yuva sayısı ve mevcut ilk-10 toplamı olan üç boyutlu bir tablo tutar. Her yüz değeri için bir sonraki katman sıfırlanır; erişilebilir bütün durumlar taranır; değeri sıfır olan durumlar atlanır; ardından o yüze atanabilecek zar sayısı 0'dan \(r\)'ye kadar denenir.
Her güncelleme tam olarak yukarıdaki yinelemeyi uygular: yeni eklenen zarların kaç tanesi hâlâ ilk 10'a girecek, dolu yuva sayısı ne olacak, kısmi toplam ne kadar artacak ve bu katkı hangi binom katsayısıyla ağırlanacak?
Tarama bittiğinde aranan sayı, 0 zar kalmış, 10 üst yuva dolmuş ve toplam 70 olmuş tablodaki hücredir. C++ uygulaması ana örneği çözmeden önce iki küçük doğrulama da yapar: \((5,6,3,15)\) örneğinin 1111 verdiğini kontrol eder ve daha küçük bir örneği kaba kuvvetle karşılaştırır. Python ve Java uygulamaları aynı dinamik programı doğrudan hedef parametreler için yürütür.
Genel \((N,F,K,S)\) parametreleri için durum sayısı \((N+1)(K+1)(S+1)\) olur. Her yüz değeri için, her durumda en fazla \(N+1\) farklı \(c\) seçeneği denenir. Bu yüzden en kötü durum çalışma süresi
$$O(F\,N^2KS)$$
seviyesindedir.
Sadece mevcut katman ile sonraki katman tutulduğu için bellek kullanımı
$$O(NKS)$$
olarak kalır. Asıl problemde \(N=20\), \(F=12\), \(K=10\), \(S=70\) olduğundan her katmanda yalnızca \(21 \cdot 11 \cdot 71 = 16401\) durum vardır.
Project Euler 240 pide contar cuántos resultados ordenados aparecen al lanzar 20 dados de 12 caras de modo que, después de ordenar los 20 valores de mayor a menor, la suma de los 10 mayores sea exactamente 70. Si la tirada ordenada es \(x_1 \ge x_2 \ge \cdots \ge x_{20}\), la condición es
$$x_1+x_2+\cdots+x_{10}=70.$$
Los dados son distinguibles antes de ordenar, así que no basta con contar multisets de caras. Si un mismo conjunto de valores puede asignarse a dados distintos de varias maneras, todas esas asignaciones son resultados válidos y deben contarse.
Las implementaciones recorren las caras desde 12 hasta 1. En cada paso deciden cuántos de los dados todavía no asignados mostrarán la cara actual, cuántas posiciones del top 10 ya han quedado forzadas por caras mayores y cuánto suma ese top parcial.
Sea \(c_v\) el número de dados que muestran la cara \(v\), con \(1 \le v \le 12\). Entonces
$$\sum_{v=1}^{12} c_v = 20.$$
Conocer \(c_{12},c_{11},\dots,c_1\) equivale a conocer la tirada ordenada: primero aparecen todos los 12, luego los 11, etc. Pero no todos esos dados entran en la suma de los 10 mayores. Si \(t_v\) es el número de dados con valor \(v\) que sí pertenecen al top 10, el recorrido descendente impone
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
Por tanto, la condición del problema se reescribe como
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
Esta observación explica por qué el algoritmo procesa las caras de mayor a menor: una vez fijadas las caras altas, la cara actual solo puede ocupar los huecos que todavía quedan dentro de los 10 mayores.
Para \(v=12,11,\dots,1\), definamos \(D_v(r,m,s)\) como el número de asignaciones parciales después de haber procesado todas las caras estrictamente mayores que \(v\). Aquí \(r\) es el número de dados aún sin asignar, \(m\) es el número de posiciones ya fijadas dentro de los 10 mayores y \(s\) es la suma aportada por esas posiciones ya fijadas.
Al inicio no se ha procesado ninguna cara, así que el único estado inicial no nulo es
$$D_{12}(20,0,0)=1.$$
Supongamos que estamos procesando la cara \(v\) desde el estado \((r,m,s)\). Elegimos \(c\) de los \(r\) dados restantes para que muestren \(v\). Eso puede hacerse de
$$\binom{r}{c}$$
formas.
De esos \(c\) dados, solamente
$$a=\min(c,10-m)$$
pueden entrar todavía en el top 10, porque quedan \(10-m\) posiciones libres y todas las caras posteriores serán menores que \(v\). La transición es entonces
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
siempre que \(s+a\,v \le 70\). Cuando \(m=10\), el top 10 ya está completamente decidido y las caras menores solo rellenan los 10 dados inferiores.
Si una tirada completa tiene multiplicidades \(c_{12},c_{11},\dots,c_1\), el barrido descendente produce el producto
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
Ese producto se simplifica a
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
que es exactamente el coeficiente multinomial que cuenta cuántas tiradas ordenadas distintas producen ese multiconjunto de caras. Esa es la razón por la que la DP cuenta resultados brutos y no solo patrones ordenados.
El ejemplo publicado usa 5 dados de 6 caras y pide que la suma de los 3 mayores sea 15; el total allí es 1111. Un solo paso local muestra bien la idea.
Supongamos que ya se ha fijado un 6 y un 5. Entonces el estado es \((r,m,s)=(3,2,11)\): quedan 3 dados sin asignar, 2 posiciones del top 3 ya están ocupadas y su suma parcial es 11. Si ahora asignamos \(c=2\) dados al valor 4, obtenemos
$$a=\min(2,3-2)=1.$$
Solo uno de esos dos cuatros puede entrar en el top 3, porque queda un único hueco. La transición lleva un factor \(\binom{3}{2}=3\) y termina en \((1,3,15)\). Si el dado restante recibe luego valor 1, el multiconjunto final es \((6,5,4,4,1)\), con
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}$$
realizaciones ordenadas. Hay dos cuatros en total, pero solo uno contribuye a la suma de los 3 mayores.
Después de procesar la cara 1, una tirada válida debe dejar 0 dados sin asignar, 10 posiciones superiores ya fijadas y suma 70. Por tanto, la respuesta buscada es
$$D_0(0,10,70).$$
Las implementaciones en C++, Python y Java construyen primero el triángulo de Pascal hasta la fila 20. Así disponen de todos los coeficientes \(\binom{r}{c}\) necesarios para la recurrencia sin recomputarlos dentro del bucle principal.
La implementación mantiene una tabla tridimensional indexada por dados restantes, plazas ya ocupadas del top 10 y suma parcial actual. Para cada cara desde 12 hasta 1 se crea una capa nueva, se recorren todos los estados alcanzables, se descartan enseguida los que tienen conteo cero y se prueban todos los posibles valores de \(c\) entre 0 y \(r\).
Cada actualización aplica exactamente la recurrencia matemática: cuántos de los nuevos dados entran todavía en el top 10, cómo cambia el número de posiciones fijadas, cómo aumenta la suma y qué factor combinatorio multiplica la contribución.
Al final del barrido, el valor buscado es la celda con 0 dados restantes, 10 plazas superiores ocupadas y suma 70. La implementación en C++ además verifica dos casos de control antes de resolver el caso principal: el ejemplo publicado \((5,6,3,15)=1111\) y otro ejemplo pequeño comparado contra fuerza bruta. Las versiones en Python y Java ejecutan la misma DP directamente sobre \((20,12,10,70)\).
Para parámetros generales \((N,F,K,S)\), el número de estados es \((N+1)(K+1)(S+1)\). Para cada una de las \(F\) caras, cada estado puede probar hasta \(N+1\) valores distintos de \(c\). El tiempo en el peor caso es, por tanto,
$$O(F\,N^2KS).$$
Como solo se guardan la capa actual y la siguiente, la memoria es
$$O(NKS).$$
En el problema concreto, con \(N=20\), \(F=12\), \(K=10\) y \(S=70\), cada capa tiene solo \(21 \cdot 11 \cdot 71 = 16401\) estados.
Project Euler 240 要求统计这样一种掷骰结果的个数：掷 20 个 12 面骰，把结果按从大到小排序后，前 10 个数的和恰好等于 70。若排序后的结果记为 \(x_1 \ge x_2 \ge \cdots \ge x_{20}\)，那么条件就是
$$x_1+x_2+\cdots+x_{10}=70.$$
这里统计的是原始有序掷骰结果，而不是只统计排序后的模式。也就是说，骰子在排序前是可区分的；同一组面值如果分配给不同的骰子，仍然要算作不同结果。因此，正确的方法必须把“多重集”恢复成真正的原始排列数。
三份实现都采用同一个思路：按面值从 12 递减到 1 逐层处理。处理当前面值时，决定还未分配的骰子中有多少个取这个值，同时记录前 10 大位置里已经被更大面值锁定了多少个，以及这些已锁定位置的部分和是多少。
设 \(c_v\) 表示点数为 \(v\) 的骰子个数，其中 \(1 \le v \le 12\)。那么必有
$$\sum_{v=1}^{12} c_v = 20.$$
一旦 \(c_{12},c_{11},\dots,c_1\) 已知，排序后的序列就完全确定：先是所有 12，再是所有 11，依此类推。但这些骰子不一定都会进入“前 10 大之和”。如果定义 \(t_v\) 为面值 \(v\) 中真正落入前 10 的个数，那么从大到小扫描时有一个确定的公式：
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
于是题目的条件等价于
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
这就是动态规划的核心不变量：较大的面值一旦固定，当前面值最多只能填补前 10 大中尚未被占据的位置。
对于 \(v=12,11,\dots,1\)，记 \(D_v(r,m,s)\) 为这样一类部分分配的数量：所有严格大于 \(v\) 的面值都已经处理完毕，目前还有 \(r\) 个骰子尚未赋值，前 10 大位置中已有 \(m\) 个被更大的面值确定下来，而这些已确定位置的和为 \(s\)。
初始时还没有处理任何面值，所以唯一非零的起始状态是
$$D_{12}(20,0,0)=1.$$
现在从状态 \((r,m,s)\) 处理面值 \(v\)。从剩余的 \(r\) 个骰子中选出 \(c\) 个赋值为 \(v\)。选择哪些带标签的骰子取这个值，一共有
$$\binom{r}{c}$$
种方法。
但这 \(c\) 个骰子里，真正还能进入前 10 的只有
$$a=\min(c,10-m)$$
个，因为前 10 大只剩 \(10-m\) 个空位，而且之后处理的面值都比 \(v\) 小，不可能反超它。因此转移为
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
前提是 \(s+a\,v \le 70\)。一旦 \(m=10\)，说明前 10 大已经完全确定，之后更小的面值只会落在后 10 个位置里，不再影响目标和。
设一个完整结果的出现次数向量是 \(c_{12},c_{11},\dots,c_1\)。按面值从大到小扫一遍时，对应的组合因子乘积为
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
这个乘积会望远镜式地化简为
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
它正是该多重集对应的原始有序掷骰结果数，也就是多项式系数。换句话说，动态规划并不是只在统计排序后的频数模式，而是在精确统计题目要求的所有原始投掷结果。
题目给出的较小样例是：掷 5 个 6 面骰，最大的 3 个点数之和为 15 时，总共有 1111 种结果。下面看一个局部转移，就能清楚看到公式的意义。
假设面值 6 和 5 已经各放入一个骰子，那么当前状态是 \((r,m,s)=(3,2,11)\)：还有 3 个骰子未赋值，前 3 大中的 2 个位置已确定，部分和为 11。现在若把其中 \(c=2\) 个骰子赋值为 4，则
$$a=\min(2,3-2)=1.$$
这两个 4 里只有一个还能进入前三，因为只剩一个空位。该转移的组合系数是 \(\binom{3}{2}=3\)，新状态变成 \((1,3,15)\)。如果最后那个骰子再赋值为 1，就得到多重集 \((6,5,4,4,1)\)。它对应的原始有序结果数为
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}.$$
可以看到，虽然一共有两个 4，但只有其中一个会计入“最大 3 个”的和。
当面值 1 也处理完以后，一个有效的完整结果必须满足：没有未赋值的骰子，前 10 大位置全部确定，而且它们的和正好是 70。因此最终答案就是
$$D_0(0,10,70).$$
C++、Python 和 Java 实现都会先把帕斯卡三角形构造到第 20 行。这样，所有需要的 \(\binom{r}{c}\) 都能直接读取，而不用在主循环里重复计算组合数。
实现中维护一个三维表，三个维度分别是剩余未赋值骰子数、已经锁定的前 10 大位置数、以及当前前 10 大的部分和。对每一个面值，从 12 递减到 1，新建下一层，然后扫描当前层所有可达状态。计数为 0 的状态会被立刻跳过；对其余状态，则尝试当前面值可以分配给多少个骰子，也就是从 0 到 \(r\) 的所有可能。
每一次更新都严格对应前面的数学递推：先算出新增骰子里有多少个仍会进入前 10，再更新已填位置数和部分和，并乘上正确的组合系数，把贡献加到下一层。
整个扫描结束后，目标计数就是“剩余骰子数为 0、前 10 个位置已填满、部分和为 70”的那个表项。C++ 实现还在求主问题之前做了两个小校验：一是验证公开样例 \((5,6,3,15)\) 的结果确实为 1111，二是把另一个更小的例子与暴力枚举进行比对。Python 和 Java 实现则直接用同一套递推计算目标参数 \((20,12,10,70)\)。
对一般参数 \((N,F,K,S)\) 而言，状态总数是 \((N+1)(K+1)(S+1)\)。每个面值都会遍历这些状态，而每个状态又最多尝试 \(N+1\) 种当前面值的分配个数，因此最坏时间复杂度为
$$O(F\,N^2KS).$$
由于实现只保留当前层和下一层两份三维表，空间复杂度为
$$O(NKS).$$
对于本题实际参数 \(N=20\)、\(F=12\)、\(K=10\)、\(S=70\)，每一层只有 \(21 \cdot 11 \cdot 71 = 16401\) 个状态，所以运行规模相当温和。
В задаче Project Euler 240 нужно посчитать число упорядоченных исходов при броске 20 двенадцатигранных кубиков, для которых сумма 10 наибольших значений после сортировки по убыванию равна 70. Если отсортированный результат записан как \(x_1 \ge x_2 \ge \cdots \ge x_{20}\), то условие имеет вид
$$x_1+x_2+\cdots+x_{10}=70.$$
Считаются именно исходные броски, а не только наборы значений. Кубики различимы до сортировки, поэтому одна и та же совокупность выпавших граней даёт несколько разных исходов, если эти значения распределены по кубикам по-разному.
Все три реализации проходят значения граней от 12 вниз до 1. На каждом шаге они выбирают, сколько ещё не назначенных кубиков получат текущую грань, сколько мест среди 10 крупнейших значений уже окончательно заняты более высокими гранями, и чему равна текущая частичная сумма этих крупнейших значений.
Пусть \(c_v\) обозначает число кубиков со значением \(v\), где \(1 \le v \le 12\). Тогда
$$\sum_{v=1}^{12} c_v = 20.$$
Как только известны числа \(c_{12},c_{11},\dots,c_1\), отсортированный список полностью определён: сначала идут все 12, затем все 11 и так далее. Но в сумму 10 наибольших входят не все эти кубики. Если \(t_v\) обозначает число кубиков со значением \(v\), которые реально попадают в верхние 10 позиций, то при проходе сверху вниз выполняется правило
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
Значит, исходное условие эквивалентно системе
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
Это и есть главный инвариант: когда большие значения уже зафиксированы, текущая грань может занять только ещё свободные места среди 10 крупнейших.
Для \(v=12,11,\dots,1\) обозначим через \(D_v(r,m,s)\) число частичных назначений после того, как все грани строго больше \(v\) уже обработаны. Здесь \(r\) означает число кубиков без значения, \(m\) число позиций среди верхних 10, уже зафиксированных более крупными гранями, а \(s\) их суммарный вклад.
В начале никакие грани ещё не обработаны, поэтому единственное ненулевое начальное состояние равно
$$D_{12}(20,0,0)=1.$$
Пусть мы обрабатываем грань \(v\) из состояния \((r,m,s)\). Выберем \(c\) из \(r\) оставшихся кубиков, которым присвоим значение \(v\). Это можно сделать
$$\binom{r}{c}$$
способами.
Из этих \(c\) кубиков только
$$a=\min(c,10-m)$$
ещё могут попасть в десятку крупнейших, потому что свободно только \(10-m\) мест, а все последующие грани будут меньше \(v\). Поэтому рекуррентный переход имеет вид
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
если \(s+a\,v \le 70\). После достижения \(m=10\) верхняя десятка полностью определена, а меньшие грани влияют уже только на нижние 10 позиций.
Если полный результат имеет кратности \(c_{12},c_{11},\dots,c_1\), то проход по граням сверху вниз даёт произведение
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
Оно телескопически сокращается до
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
то есть ровно до мультиномиального коэффициента, который считает количество различных упорядоченных бросков с таким набором граней. Следовательно, динамика считает именно сырые результаты, а не только отсортированные гистограммы.
В опубликованном примере используются 5 шестигранных кубиков, и сумма 3 наибольших значений должна быть 15; ответ там равен 1111. Один локальный переход хорошо показывает смысл формулы.
Предположим, что значения 6 и 5 уже заняли по одному месту. Тогда состояние равно \((r,m,s)=(3,2,11)\): остаётся 3 кубика без значения, 2 места среди верхних 3 уже определены, их частичная сумма равна 11. Если теперь присвоить \(c=2\) кубикам значение 4, то
$$a=\min(2,3-2)=1.$$
Только одна из этих двух четвёрок сможет попасть в верхнюю тройку, потому что свободно лишь одно место. Коэффициент перехода равен \(\binom{3}{2}=3\), а новое состояние становится \((1,3,15)\). Если последний кубик затем получит значение 1, получится мультимножество \((6,5,4,4,1)\), которому соответствует
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}$$
упорядоченных реализаций. Хотя четвёрок две, в сумму трёх наибольших попадает только одна из них.
После обработки грани 1 корректный полный бросок должен иметь 0 неназначенных кубиков, все 10 верхних мест должны быть определены, а их сумма должна равняться 70. Значит, искомый ответ равен
$$D_0(0,10,70).$$
Реализации на C++, Python и Java сначала строят треугольник Паскаля до строки 20. Тем самым все коэффициенты \(\binom{r}{c}\), нужные в рекуррентной формуле, доступны заранее.
В программе хранится трёхмерная таблица с осями: число оставшихся кубиков, число уже заполненных мест в верхней десятке и текущая частичная сумма. Для каждой грани от 12 до 1 создаётся следующий слой, затем перебираются все достижимые состояния, нулевые состояния сразу пропускаются, и для каждого состояния пробуются все возможные значения \(c\) от 0 до \(r\).
Каждое обновление буквально реализует математический переход: вычисляется, сколько новых кубиков ещё попадает в верхние 10, как меняются число занятых позиций и сумма, и с каким биномиальным коэффициентом нужно добавить вклад.
После завершения прохода искомый результат находится в ячейке с 0 оставшихся кубиков, 10 занятыми верхними позициями и суммой 70. Реализация на C++ дополнительно выполняет две проверки: сверяет опубликованный пример \((5,6,3,15)=1111\) и сравнивает ещё один небольшой случай с полным перебором. Реализации на Python и Java запускают ту же динамику напрямую для параметров \((20,12,10,70)\).
Для общих параметров \((N,F,K,S)\) размер пространства состояний равен \((N+1)(K+1)(S+1)\). Для каждой из \(F\) граней в каждом состоянии перебирается до \(N+1\) вариантов для \(c\). Поэтому в худшем случае время работы составляет
$$O(F\,N^2KS).$$
Поскольку хранятся только текущий и следующий слои, память равна
$$O(NKS).$$
Для конкретной задачи \(N=20\), \(F=12\), \(K=10\), \(S=70\) каждый слой содержит лишь \(21 \cdot 11 \cdot 71 = 16401\) состояний, так что алгоритм работает с большим запасом.
تطلب مسألة Project Euler 240 عدَّ عدد النتائج المرتبة الناتجة من رمي 20 نردًا لكل واحد منها 12 وجهًا، بحيث يكون مجموع أكبر 10 قيم بعد ترتيب النتائج تنازليًا مساويًا تمامًا لـ 70. إذا كتبنا النتيجة المرتبة على الصورة \(x_1 \ge x_2 \ge \cdots \ge x_{20}\)، فالشرط هو
$$x_1+x_2+\cdots+x_{10}=70.$$
العد هنا يخص الرميات الخام المرتبة قبل الفرز، لا مجرد الأنماط بعد الترتيب. فالنرود مميزة قبل الفرز، ولذلك فإن نفس مجموعة القيم تُحسب بعدة طرق إذا وُزعت على نرود مختلفة.
تعتمد جميع التطبيقات على المرور على قيم الأوجه من 12 نزولًا إلى 1. في كل خطوة نحدد كم نردًا من النرود غير المعينة بعد سيأخذ القيمة الحالية، وكم موضعًا من أكبر 10 مواضع صار محسومًا بالفعل بسبب القيم الأعلى، وما هو المجموع الجزئي لهذه المواضع المحسومة.
ليكن \(c_v\) عدد النرود التي تظهر القيمة \(v\)، حيث \(1 \le v \le 12\). عندئذٍ
$$\sum_{v=1}^{12} c_v = 20.$$
متى عُرفت القيم \(c_{12},c_{11},\dots,c_1\)، أصبحت اللائحة المرتبة معروفة بالكامل: جميع الـ 12 أولًا، ثم جميع الـ 11، وهكذا. لكن ليست كل هذه النرود تدخل في مجموع أكبر 10 قيم. إذا رمزنا بـ \(t_v\) إلى عدد النرود ذات القيمة \(v\) التي تدخل فعلًا ضمن أكبر 10، فإن المسح من الأعلى إلى الأدنى يعطي العلاقة
$$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$$
وهكذا يصبح شرط المسألة مكافئًا لـ
$$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$$
وهذا هو الثابت الأساسي في البرمجة الديناميكية: بعد تثبيت القيم الأكبر، لا تستطيع القيمة الحالية إلا أن تملأ الخانات المتبقية ضمن أكبر 10.
لكل \(v=12,11,\dots,1\)، نرمز بـ \(D_v(r,m,s)\) إلى عدد التعيينات الجزئية بعد الانتهاء من جميع الأوجه الأكبر من \(v\). هنا \(r\) هو عدد النرود التي لم تُعط قيمة بعد، و\(m\) هو عدد المواضع المحسومة داخل أكبر 10، و\(s\) هو مجموع هذه المواضع المحسومة.
في البداية لم تتم معالجة أي وجه، ولذلك فإن الحالة الابتدائية الوحيدة غير الصفرية هي
$$D_{12}(20,0,0)=1.$$
افترض أننا نعالج الوجه \(v\) انطلاقًا من الحالة \((r,m,s)\). نختار \(c\) من بين \(r\) نرود متبقية لتأخذ القيمة \(v\). عدد طرق اختيار هذه النرود المميزة هو
$$\binom{r}{c}.$$
لكن عدد ما سيدخل فعلًا ضمن أكبر 10 من هذه النرود لا يتجاوز
$$a=\min(c,10-m),$$
لأنه لا يوجد سوى \(10-m\) مواضع شاغرة، وجميع الأوجه التي ستأتي لاحقًا أصغر من \(v\). لذلك تكون العلاقة
$$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$$
بشرط أن يكون \(s+a\,v \le 70\). وعندما يصل \(m\) إلى 10 تكون أكبر 10 قيم قد تحددت بالكامل، ولا تعود الأوجه الأصغر تؤثر إلا في النصف السفلي من النتيجة.
إذا كانت النتيجة الكاملة تملك التكرارات \(c_{12},c_{11},\dots,c_1\)، فإن المرور التنازلي يولد حاصل الضرب
$$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$$
وهذا يتبسط إلى
$$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$$
وهو بالضبط المعامل متعدد الحدود الذي يعطي عدد الرميات المرتبة الموافقة لذلك التوزيع من القيم. لهذا السبب لا تكتفي الطريقة بعدِّ الأنماط المرتبة، بل تعد جميع النتائج الأولية التي تطلبها المسألة.
المثال المنشور في نص المسألة يستخدم 5 نرود سداسية الأوجه، ويطلب أن يكون مجموع أكبر 3 قيم مساويًا لـ 15، والعدد الكلي هناك هو 1111. انتقال واحد محلي يوضح الفكرة جيدًا.
لنفترض أن القيمتين 6 و5 قد ظهرتا مرة واحدة لكل منهما. عندها تكون الحالة \((r,m,s)=(3,2,11)\): بقيت 3 نرود بلا تعيين، وحُسم موضعان من أكبر 3، والمجموع الجزئي هو 11. إذا أعطينا الآن \(c=2\) من هذه النرود القيمة 4، فإن
$$a=\min(2,3-2)=1.$$
واحد فقط من هذين العددين 4 يمكنه دخول أكبر 3، لأن موضعًا واحدًا فقط ما زال شاغرًا. يحمل الانتقال العامل \(\binom{3}{2}=3\)، وتصبح الحالة الجديدة \((1,3,15)\). إذا أُعطي النرد الأخير بعد ذلك القيمة 1، حصلنا على التعدد \((6,5,4,4,1)\)، وعدد ترتيباته الخام هو
$$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}.$$
إذًا يوجد رقمان 4 فعلًا، لكن واحدًا منهما فقط يشارك في مجموع أكبر 3 قيم.
بعد معالجة الوجه 1 أيضًا، لا تكون الرمية صالحة إلا إذا لم يبق أي نرد بلا قيمة، وتم حسم جميع المواضع العشرة العليا، وكان مجموعها 70. لذلك فالجواب النهائي هو
$$D_0(0,10,70).$$
تبني تطبيقات C++ وPython وJava مثلث باسكال حتى الصف 20. بهذا تصبح جميع القيم \(\binom{r}{c}\) المطلوبة في علاقة الانتقال متاحة مسبقًا.
يحتفظ التنفيذ بجدول ثلاثي الأبعاد مفهرس بعدد النرود المتبقية، وعدد المواضع المحسومة في أكبر 10، والمجموع الجزئي الحالي. لكل قيمة وجه من 12 حتى 1 تُنشأ طبقة تالية، ثم تُفحص كل الحالات الممكنة الوصول إليها، وتُتجاوز الحالات الصفرية مباشرة، وبعد ذلك تُجرَّب جميع القيم الممكنة لـ \(c\) من 0 إلى \(r\).
كل تحديث يطبق العلاقة الرياضية حرفيًا: يُحسب عدد النرود الجديدة التي ما زالت تدخل ضمن أكبر 10، ثم يُحدَّث عدد المواضع المحسومة والمجموع، ويُضرب الإسهام في معامل الاختيار الصحيح.
بعد انتهاء المرور الكامل، تكون النتيجة المطلوبة هي الخانة التي تحقق 0 نرد متبقٍ و10 مواضع عليا محسومة ومجموعًا يساوي 70. تضيف نسخة C++ أيضًا فحصين صغيرين قبل حل الحالة الأساسية: تتحقق من أن المثال المنشور \((5,6,3,15)\) يعطي 1111، وتقارن حالة أصغر أخرى بعدٍّ brute-force. أما نسختا Python وJava فتطبقان نفس البرمجة الديناميكية مباشرة على المعلمات \((20,12,10,70)\).
للمعلمات العامة \((N,F,K,S)\)، يكون عدد الحالات \((N+1)(K+1)(S+1)\). ولكل واحد من الأوجه \(F\)، يمكن لكل حالة أن تجرب حتى \(N+1\) قيم مختلفة لـ \(c\). لذا فإن تعقيد الزمن في أسوأ الأحوال هو
$$O(F\,N^2KS).$$
وبما أن التنفيذ يحتفظ فقط بالطبقة الحالية والطبقة التالية، فإن تعقيد الذاكرة يساوي
$$O(NKS).$$
في المسألة الفعلية حيث \(N=20\) و\(F=12\) و\(K=10\) و\(S=70\)، تحتوي كل طبقة على \(21 \cdot 11 \cdot 71 = 16401\) حالة فقط، لذلك تكون الطريقة مريحة عمليًا.