In this darts setting, a checkout may use one, two, or three darts, but the final dart must land in a double. The goal is to count how many distinct checkouts produce a total score strictly below \(100\).
The important word is distinct. Different landing regions are counted separately even when they have the same numerical value. For example, \(S6\), \(D3\), and \(T2\) all score \(6\), but they are different darts and therefore different non-final choices. The solution must count regions, not just totals.
Let \(A\) be the set of all legal non-final darts and \(F\) the set of legal finishing darts. Then
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
and
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
If \(v(x)\) denotes the score of region \(x\), the problem becomes a finite counting problem on these two sets.
Only the final dart keeps its position in the ordering. The first two darts may be swapped without creating a new checkout, so the preliminary part is best modeled as a multiset of size \(0\), \(1\), or \(2\) drawn from \(A\). Size \(0\) corresponds to a one-dart checkout, size \(1\) to a two-dart checkout, and size \(2\) to a three-dart checkout.
This viewpoint also explains why misses are absent from the implementations. A shorter checkout is already represented by choosing fewer preliminary darts, so explicit misses would duplicate cases rather than create new ones.
Write \(A=\{a_1,\dots,a_{62}\}\). For a score limit \(L\), every valid checkout is counted exactly once by
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
Here \(\mathbf{1}(\cdot)\) is the indicator function: it contributes \(1\) when the inequality is true and \(0\) otherwise. The condition \(i\le j\) is exactly the mathematical statement that the first two darts are unordered, while repetition such as \(\{D1,D1\}\) is still allowed.
Before imposing the bound \(L=100\), the total number of formal checkout patterns is easy to compute. There are \(21\) one-dart finishes, \(62\cdot 21\) two-dart finishes, and
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
three-dart finishes, because the first two darts form a two-element multiset chosen from \(62\) region types. Therefore the unrestricted search space has
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
distinct formal checkouts. The actual Project Euler task is simply the subset of these patterns whose total score is below \(100\).
A good sanity check is \(L=6\). Only \(D1\) and \(D2\) can be finishing doubles, because \(D3=6\) already fails the strict inequality.
If the checkout ends on \(D1\), the preliminary darts must total less than \(4\). That gives one empty preliminary multiset, five one-dart choices \((S1,S2,D1,S3,T1)\), and three two-dart multisets \(\{S1,S1\}\), \(\{S1,S2\}\), and \(\{S1,D1\}\). So finishes ending on \(D1\) contribute \(1+5+3=9\) checkouts.
If the checkout ends on \(D2\), the preliminary darts must total less than \(2\). The only possibilities are the empty multiset and the single dart \(S1\), so finishes ending on \(D2\) contribute \(2\) more checkouts. Hence
$$C(6)=9+2=11.$$
This example also shows why region identity matters: \(S3\) and \(T1\) both score \(3\), but they remain distinct checkouts when followed by \(D1\).
The C++, Python, and Java implementations first construct the two lists dictated by the mathematics: the \(62\) legal non-final regions and the \(21\) legal finishing doubles. Each entry stores both a label and its numerical score, so later checks are simple additions and comparisons.
They then perform three passes that match the three terms in the formula. The first counts one-dart finishes. The second pairs every non-final region with every finishing double. The third enumerates two preliminary darts as an unordered pair by starting the second loop at the current position of the first, which keeps repetitions while avoiding double-counting from swapped order.
Every candidate pattern is accepted exactly when its total is strictly less than the limit. The C++ implementation exposes that limit as a parameter and verifies the smaller case \(L=6\); the Python and Java implementations evaluate the same enumeration directly for \(L=100\).
The candidate space is tiny. There are \(21\) one-dart cases, \(62\cdot 21=1302\) two-dart cases, and \(\binom{63}{2}\cdot 21=41013\) three-dart cases, for a total of \(42336\) candidates before filtering. That is why direct enumeration is not merely acceptable here; it is the natural exact method.
In generalized notation the runtime is \(O(|F|\cdot |A|^2)\), dominated by the unordered two-preliminary-dart sweep. Memory usage is \(O(|A|+|F|)\) for the two region lists, which is constant for the fixed dartboard in the problem.
In diesem Dartszenario darf ein Checkout aus einem, zwei oder drei Würfen bestehen, aber der letzte Wurf muss ein Double sein. Gesucht ist die Anzahl aller verschiedenen Checkouts, deren Gesamtpunktzahl strikt kleiner als \(100\) ist.
Entscheidend ist das Wort verschieden. Unterschiedliche Trefferfelder werden separat gezählt, auch wenn sie dieselbe Punktzahl liefern. Zum Beispiel haben \(S6\), \(D3\) und \(T2\) alle den Wert \(6\), sind aber drei verschiedene Würfe und müssen deshalb als unterschiedliche nicht-letzte Optionen behandelt werden. Gezählt werden also Felder, nicht bloß Summen.
Sei \(A\) die Menge aller erlaubten nicht-letzten Würfe und \(F\) die Menge aller erlaubten Abschlusswürfe. Dann gilt
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
und
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
Bezeichnet \(v(x)\) die Punktzahl des Feldes \(x\), dann reduziert sich die Aufgabe auf ein endliches Zählproblem über diesen beiden Mengen.
Nur der letzte Wurf behält seine feste Position in der Reihenfolge. Die ersten beiden Würfe dürfen vertauscht werden, ohne einen neuen Checkout zu erzeugen. Daher modelliert man den Anfangsteil am besten als Multiset der Größe \(0\), \(1\) oder \(2\) aus \(A\). Größe \(0\) steht für einen Ein-Dart-Checkout, Größe \(1\) für einen Zwei-Dart-Checkout und Größe \(2\) für einen Drei-Dart-Checkout.
Genau dadurch wird auch klar, warum Fehlwürfe in den Implementierungen nicht vorkommen. Ein kürzerer Checkout ist bereits dadurch beschrieben, dass man weniger Vorwürfe auswählt; explizite Misses würden nur Fälle duplizieren.
Schreibe \(A=\{a_1,\dots,a_{62}\}\). Für ein Limit \(L\) wird jeder gültige Checkout genau einmal durch
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr)$$
gezählt. Dabei ist \(\mathbf{1}(\cdot)\) die Indikatorfunktion: Sie liefert \(1\), wenn die Ungleichung erfüllt ist, und sonst \(0\). Die Bedingung \(i\le j\) ist genau die mathematische Formulierung dafür, dass die ersten beiden Würfe ungeordnet sind, Wiederholungen wie \(\{D1,D1\}\) aber trotzdem erlaubt bleiben.
Ohne die Schranke \(L=100\) lässt sich die Gesamtzahl der formalen Checkout-Muster leicht bestimmen. Es gibt \(21\) Ein-Dart-Abschlüsse, \(62\cdot 21\) Zwei-Dart-Abschlüsse und
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
Drei-Dart-Abschlüsse, denn die ersten beiden Würfe bilden ein Zweier-Multiset aus \(62\) Feldtypen. Damit hat der unbeschränkte Suchraum insgesamt
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
verschiedene formale Checkouts. Die eigentliche Aufgabe ist einfach die Teilmenge davon mit Gesamtpunktzahl unter \(100\).
Ein nützlicher Testfall ist \(L=6\). Als Abschlussdoubles kommen nur \(D1\) und \(D2\) infrage, denn \(D3=6\) verletzt die strikte Ungleichung bereits.
Endet der Checkout auf \(D1\), dann müssen die Vorwürfe zusammen kleiner als \(4\) sein. Das ergibt ein leeres Vorwurf-Multiset, fünf Ein-Dart-Möglichkeiten \((S1,S2,D1,S3,T1)\) und drei Zwei-Dart-Multisets \(\{S1,S1\}\), \(\{S1,S2\}\) und \(\{S1,D1\}\). Abschlüsse mit Endwurf \(D1\) liefern also \(1+5+3=9\) Checkouts.
Endet der Checkout auf \(D2\), dann müssen die Vorwürfe zusammen kleiner als \(2\) sein. Möglich sind nur das leere Multiset und der einzelne Wurf \(S1\), also kommen weitere \(2\) Checkouts hinzu. Folglich gilt
$$C(6)=9+2=11.$$
Dieses Beispiel zeigt zugleich, warum die Identität des Feldes wichtig ist: \(S3\) und \(T1\) haben beide den Wert \(3\), bleiben aber unterschiedliche Checkouts, wenn anschließend \(D1\) geworfen wird.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst genau die beiden Listen, die im mathematischen Modell vorkommen: die \(62\) erlaubten nicht-letzten Felder und die \(21\) erlaubten Abschlussdoubles. Zu jedem Eintrag wird neben der Bezeichnung auch sein Zahlenwert gespeichert, sodass später nur noch addiert und verglichen werden muss.
Danach folgen drei Zähldurchgänge, die exakt den drei Summanden der Formel entsprechen. Der erste zählt Ein-Dart-Abschlüsse. Der zweite kombiniert jedes nicht-letzte Feld mit jedem Abschlussdouble. Der dritte enumeriert zwei Vorwürfe als ungeordnetes Paar, indem die zweite Schleife erst bei der aktuellen Position der ersten beginnt; so bleiben Wiederholungen erhalten, aber Vertauschungen werden nicht doppelt gezählt.
Jedes Kandidatenmuster wird genau dann akzeptiert, wenn seine Gesamtpunktzahl strikt kleiner als das Limit ist. Die C++-Version parametrisiert dieses Limit und überprüft den kleineren Fall \(L=6\); die Python- und Java-Versionen werten dieselbe Enumeration direkt für \(L=100\) aus.
Der Kandidatenraum ist sehr klein. Es gibt \(21\) Ein-Dart-Fälle, \(62\cdot 21=1302\) Zwei-Dart-Fälle und \(\binom{63}{2}\cdot 21=41013\) Drei-Dart-Fälle, also insgesamt \(42336\) Kandidaten vor dem Filtern. Deshalb ist direkte Enumeration hier nicht nur praktikabel, sondern die natürliche exakte Methode.
In verallgemeinerter Schreibweise beträgt die Laufzeit \(O(|F|\cdot |A|^2)\), dominiert durch den Durchlauf über ungeordnete Paare der ersten beiden Würfe. Der Speicherbedarf ist \(O(|A|+|F|)\) für die beiden Listen und damit beim festen Dartboard der Aufgabe konstant.
Bu dart probleminde bir checkout bir, iki veya üç darttan oluşabilir; ancak son dart mutlaka bir double olmalıdır. Amaç, toplam skoru \(100\)'den kesin olarak küçük olan farklı checkout sayısını bulmaktır.
Buradaki kritik nokta farklı kelimesidir. Aynı sayısal skoru veren farklı bölgeler ayrı ayrı sayılır. Örneğin \(S6\), \(D3\) ve \(T2\) üçü de \(6\) puan eder, fakat bunlar farklı atışlardır ve son darttan önce kullanıldıklarında ayrı seçenekler olarak kalırlar. Dolayısıyla yalnızca puanları değil, gerçekten vurulan bölgeleri saymak gerekir.
\(A\), son dart dışında izin verilen tüm atışların kümesi; \(F\) ise bitirici dartların kümesi olsun. O zaman
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
ve
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
Bir bölgenin puanını \(v(x)\) ile gösterirsek, bütün problem bu iki küme üzerinde yapılan sonlu bir sayım problemine dönüşür.
Sıralamadaki yeri gerçekten önemli olan tek atış son darttır. İlk iki dart yer değiştirirse yeni bir checkout oluşmaz. Bu yüzden başlangıç kısmını, \(A\) kümesinden seçilmiş büyüklüğü \(0\), \(1\) veya \(2\) olan bir multiset olarak modellemek en doğrusudur. Büyüklük \(0\) tek dartta bitişi, büyüklük \(1\) iki dartta bitişi, büyüklük \(2\) ise üç dartta bitişi temsil eder.
Bu bakış açısı, uygulamalarda neden ıskaların bulunmadığını da açıklar. Daha kısa bir checkout zaten daha az ön dart seçilerek temsil edilir; açıkça bir miss eklemek yeni durum üretmez, sadece aynı durumu tekrarlar.
\(A=\{a_1,\dots,a_{62}\}\) yazalım. Bir \(L\) limiti için her geçerli checkout tam olarak bir kez şu ifadeyle sayılır:
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
Buradaki \(\mathbf{1}(\cdot)\) gösterge fonksiyonudur; eşitsizlik doğruysa \(1\), değilse \(0\) verir. \(i\le j\) koşulu da ilk iki dartın sırasız olduğunu, ama \(\{D1,D1\}\) gibi tekrarların hâlâ geçerli kaldığını matematiksel olarak ifade eder.
\(L=100\) sınırı hiç uygulanmadan önce toplam checkout kalıp sayısını kapalı biçimde yazabiliriz. \(21\) tane tek dartlı bitiş, \(62\cdot 21\) tane iki dartlı bitiş ve
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
tane üç dartlı bitiş vardır; çünkü ilk iki dart, \(62\) bölge tipinden seçilen iki elemanlı tekrarlı kombinasyondur. Böylece sınır konmadan önce toplam
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
farklı biçimsel checkout oluşur. Asıl görev, bunların toplam puanı \(100\)'den küçük olan alt kümesini saymaktır.
İyi bir sağlamlık kontrolü \(L=6\) durumudur. Bitirici double olarak yalnızca \(D1\) ve \(D2\) kalır; çünkü \(D3=6\) artık sıkı eşitsizliği sağlamaz.
Checkout \(D1\) ile bitiyorsa, önceki dartların toplamı \(4\)'ten küçük olmalıdır. Bu da bir boş multiset, beş tek-dart seçeneği \((S1,S2,D1,S3,T1)\) ve üç iki-dart multiset'i \(\{S1,S1\}\), \(\{S1,S2\}\), \(\{S1,D1\}\) verir. Yani son dartı \(D1\) olan toplam \(1+5+3=9\) checkout vardır.
Checkout \(D2\) ile bitiyorsa, önceki dartların toplamı \(2\)'den küçük olmalıdır. Burada yalnızca boş multiset ile tek dart \(S1\) mümkündür; yani \(2\) checkout daha gelir. Sonuç olarak
$$C(6)=9+2=11.$$
Bu örnek ayrıca bölge kimliğinin neden önemli olduğunu da gösterir: \(S3\) ile \(T1\) ikisi de \(3\) puan eder, ama ardından \(D1\) gelince hâlâ iki farklı checkout olarak sayılırlar.
C++, Python ve Java uygulamaları önce matematikte tanımlanan iki listeyi kurar: son dart dışında izin verilen \(62\) bölge ve bitiriş için izin verilen \(21\) double. Her giriş için hem etiket hem de sayısal puan tutulur; böylece geri kalan adımlar basit toplama ve karşılaştırmalara iner.
Ardından formüldeki üç terime karşılık gelen üç sayım geçişi yapılır. İlk geçiş yalnızca bitirici double'dan oluşan tek dartlı finişleri sayar. İkinci geçiş, her ön dartı her bitirici double ile eşler. Üçüncü geçişte ise iki ön dart sırasız bir çift olarak taranır; ikinci döngünün ilk döngünün bulunduğu yerden başlaması sayesinde tekrarlar korunur, ama aynı iki dartın yer değiştirmesi ikinci kez sayılmaz.
Her aday desen için tek kontrol toplam puanın limitten küçük olmasıdır. C++ uygulaması bu limiti parametre olarak alır ve daha küçük \(L=6\) örneğiyle doğrulama yapar; Python ve Java uygulamaları ise aynı sayımı doğrudan \(L=100\) için uygular.
Aday uzayı çok küçüktür. \(21\) tek dartlı durum, \(62\cdot 21=1302\) iki dartlı durum ve \(\binom{63}{2}\cdot 21=41013\) üç dartlı durum vardır; filtrelemeden önce toplam \(42336\) aday incelenir. Bu yüzden doğrudan numaralandırma burada sadece yeterli değil, aynı zamanda en doğal kesin yöntemdir.
Genelleştirilmiş gösterimde çalışma süresi \(O(|F|\cdot |A|^2)\) olur; baskın kısım sırasız iki ön dart taramasıdır. Bellek kullanımı iki bölge listesini tutmak için \(O(|A|+|F|)\) düzeyindedir ve problemdeki sabit dart tahtası için bu fiilen sabittir.
En esta versión del juego de dardos, un checkout puede usar uno, dos o tres lanzamientos, pero el último debe caer obligatoriamente en un doble. La tarea consiste en contar cuántos checkouts distintos producen una puntuación total estrictamente menor que \(100\).
La palabra clave es distintos. Dos regiones del tablero siguen contando por separado aunque den la misma puntuación numérica. Por ejemplo, \(S6\), \(D3\) y \(T2\) valen \(6\), pero representan lanzamientos diferentes y por eso deben distinguirse en las posiciones no finales. El conteo correcto trabaja con regiones etiquetadas, no solo con sumas.
Sea \(A\) el conjunto de todos los lanzamientos permitidos antes del último dardo y sea \(F\) el conjunto de todos los lanzamientos finales permitidos. Entonces
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
y
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
Si \(v(x)\) denota la puntuación de la región \(x\), todo el problema se convierte en un conteo finito sobre esos dos conjuntos.
Solo el último dardo conserva una posición distinguida en el orden. Los dos primeros pueden intercambiarse sin crear un checkout nuevo, así que la parte previa se modela mejor como un multiconjunto de tamaño \(0\), \(1\) o \(2\) tomado de \(A\). Tamaño \(0\) significa checkout de un solo dardo, tamaño \(1\) significa checkout de dos dardos y tamaño \(2\) significa checkout de tres dardos.
Este punto de vista también explica por qué no hace falta representar fallos. Un checkout más corto ya está descrito eligiendo menos dardos previos, de modo que añadir misses explícitos solo duplicaría casos existentes.
Escribamos \(A=\{a_1,\dots,a_{62}\}\). Para un límite \(L\), cada checkout válido se cuenta exactamente una vez mediante
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
Aquí \(\mathbf{1}(\cdot)\) es la función indicadora: vale \(1\) cuando la desigualdad se cumple y \(0\) en caso contrario. La condición \(i\le j\) expresa exactamente que los dos primeros dardos no están ordenados, aunque sí se permite repetir una misma región, como en \(\{D1,D1\}\).
Antes de imponer \(L=100\), el número total de patrones formales es fácil de obtener. Hay \(21\) finales de un dardo, \(62\cdot 21\) finales de dos dardos y
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
finales de tres dardos, porque los dos primeros forman un multiconjunto de dos elementos elegidos entre \(62\) tipos de región. Por tanto, el espacio completo sin filtrar contiene
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
checkouts formales distintos. El problema real solo pide el subconjunto cuya suma total es menor que \(100\).
Una comprobación útil es \(L=6\). Los únicos dobles finales posibles son \(D1\) y \(D2\), porque \(D3=6\) ya no satisface la desigualdad estricta.
Si el checkout termina en \(D1\), los dardos previos deben sumar menos de \(4\). Eso produce un multiconjunto vacío, cinco opciones de un solo dardo \((S1,S2,D1,S3,T1)\) y tres multiconjuntos de dos dardos: \(\{S1,S1\}\), \(\{S1,S2\}\) y \(\{S1,D1\}\). En total, los finales que acaban en \(D1\) aportan \(1+5+3=9\) checkouts.
Si el checkout termina en \(D2\), los dardos previos deben sumar menos de \(2\). Solo son posibles el multiconjunto vacío y el único dardo \(S1\), así que aparecen \(2\) checkouts más. Luego
$$C(6)=9+2=11.$$
Este ejemplo también deja claro por qué importa la identidad de la región: \(S3\) y \(T1\) valen \(3\), pero siguen siendo checkouts distintos cuando van seguidos de \(D1\).
Las implementaciones en C++, Python y Java construyen primero las dos listas que aparecen en el modelo matemático: las \(62\) regiones válidas antes del último dardo y los \(21\) dobles que pueden cerrar la jugada. Cada entrada conserva su etiqueta y su valor numérico, de modo que luego todo se reduce a sumar y comparar.
Después realizan tres recorridos de conteo, uno por cada término de la fórmula. El primero cuenta cierres de un solo dardo. El segundo combina cada región no final con cada doble final. El tercero recorre dos dardos previos como un par no ordenado, arrancando el segundo índice desde la posición actual del primero; así se permiten repeticiones, pero se evita contar dos veces el mismo par en orden invertido.
Cada patrón candidato se acepta exactamente cuando su puntuación total es estrictamente menor que el límite. La implementación en C++ deja ese límite como parámetro y verifica el caso pequeño \(L=6\); las de Python y Java evalúan la misma enumeración directamente con \(L=100\).
El espacio de candidatos es muy pequeño. Hay \(21\) casos de un dardo, \(62\cdot 21=1302\) casos de dos dardos y \(\binom{63}{2}\cdot 21=41013\) casos de tres dardos, para un total de \(42336\) candidatos antes del filtrado. Por eso la enumeración directa no solo es viable, sino que es el método exacto más natural.
En notación general, el tiempo de ejecución es \(O(|F|\cdot |A|^2)\), dominado por el recorrido de pares no ordenados de dardos previos. El uso de memoria es \(O(|A|+|F|)\) para almacenar las dos listas, lo cual es constante en el tablero fijo de este problema.
在这道飞镖题里，一次 checkout 可以用 \(1\)、\(2\) 或 \(3\) 支镖完成，但最后一镖必须落在 double 区域。目标是统计总得分严格小于 \(100\) 的不同 checkout 一共有多少种。
这里“不同”指的是命中的具体区域不同，而不只是数值不同。比如 \(S6\)、\(D3\) 和 \(T2\) 的分值都等于 \(6\)，但它们代表三个不同的落点，因此在最后一镖之前都必须分别计数。换句话说，解法的基本对象不是“某个分数”，而是“棋盘上的命中区域”。
记 \(A\) 为所有允许出现在最后一镖之前的区域集合，记 \(F\) 为所有允许作为收尾的区域集合。于是
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
并且
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
如果用 \(v(x)\) 表示区域 \(x\) 的分值，那么整道题就变成了在这两个有限集合上做精确计数。
顺序真正固定的只有最后一镖。前两镖互换次序并不会产生新的 checkout，所以最自然的建模方式，是把前置部分看成从 \(A\) 中选出的一个大小为 \(0\)、\(1\) 或 \(2\) 的多重集合。大小为 \(0\) 表示一镖结束，大小为 \(1\) 表示两镖结束，大小为 \(2\) 表示三镖结束。
这一点同时解释了为什么实现里不需要显式加入 miss。更短的 checkout 已经由“少选一支前置镖”表示出来了；如果再把 miss 当成单独对象，只会把原本已经存在的情况重复一遍。
把 \(A\) 写成 \(A=\{a_1,\dots,a_{62}\}\)。对于任意上界 \(L\)，所有合法 checkout 可以恰好一次地由下面的公式计数：
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
其中 \(\mathbf{1}(\cdot)\) 是示性函数：条件成立时取 \(1\)，否则取 \(0\)。约束 \(i\le j\) 正好对应“前两镖无序，但允许重复”这一题意，因此像 \(\{D1,D1\}\) 这样的组合也会被保留，而 \((S1,T1)\) 与 \((T1,S1)\) 不会被重复计算。
如果先不加 \(L=100\) 这个限制，形式上的 checkout 总数可以直接算出来。单镖结束有 \(21\) 种，两镖结束有 \(62\cdot 21\) 种，而三镖结束有
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
种，因为前两镖本质上是从 \(62\) 种区域类型里选出的一个大小为 \(2\) 的多重集合。因此，不加分数限制时一共有
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
种不同的形式化 checkout。题目真正要的，只是其中总分小于 \(100\) 的那一部分。
一个很好的校验例子是 \(L=6\)。这时能作为最后一镖的 double 只有 \(D1\) 和 \(D2\)，因为 \(D3=6\) 已经不满足严格小于 \(6\) 的要求。
如果最后一镖是 \(D1\)，那么前面所有镖的总分必须小于 \(4\)。这时有一种空多重集合、五种单镖选择 \((S1,S2,D1,S3,T1)\)，以及三种两镖多重集合 \(\{S1,S1\}\)、\(\{S1,S2\}\)、\(\{S1,D1\}\)。所以以 \(D1\) 收尾的 checkout 一共贡献 \(1+5+3=9\) 种。
如果最后一镖是 \(D2\)，那么前面部分必须小于 \(2\)。此时只有空多重集合和单镖 \(S1\) 两种可能，因此再贡献 \(2\) 种。于是
$$C(6)=9+2=11.$$
这个例子也清楚说明了“区域身份不能合并”这一不变量：\(S3\) 和 \(T1\) 都是 \(3\) 分，但接上 \(D1\) 以后它们仍然是两个不同的 checkout。
C++、Python 和 Java 的实现首先构造与数学模型完全一致的两张表：\(62\) 个允许出现在最后一镖之前的区域，以及 \(21\) 个允许作为收尾的 double。每个条目都同时保存标签和分值，因此后续逻辑只需要做整数加法与比较。
接下来代码做三轮计数，对应公式中的三项。第一轮只统计“最后一镖单独结束”的情况。第二轮把每个前置区域与每个收尾 double 配对。第三轮枚举前两镖的无序对：第二层循环从第一层当前的位置开始，这样既保留了重复选择同一区域的情况，也自动避免了把交换顺序后的同一组合算两次。
每个候选模式都用同一个条件筛选：总分必须严格小于给定上界。C++ 实现把上界写成参数，并额外检查了 \(L=6\) 这个小例子；Python 和 Java 实现则直接在 \(L=100\) 上执行同样的枚举。
候选空间非常小。单镖情况有 \(21\) 个，两镖情况有 \(62\cdot 21=1302\) 个，三镖情况有 \(\binom{63}{2}\cdot 21=41013\) 个，因此筛选前总共只有 \(42336\) 个候选模式。这也是为什么直接枚举不仅可行，而且正是这道题最自然的精确做法。
若写成一般形式，时间复杂度是 \(O(|F|\cdot |A|^2)\)，主导部分是前两镖无序对的遍历。空间复杂度是 \(O(|A|+|F|)\)，仅用于保存两张区域表；在题目固定的飞镖盘上，这实际上就是常数空间。
В этой задаче о дартсе чекаут может состоять из одного, двух или трёх бросков, но последний бросок обязан попасть в дабл. Нужно посчитать, сколько различных чекаутов дают суммарный счёт строго меньше \(100\).
Ключевое слово здесь - различных. Разные сектора доски считаются отдельно, даже если приносят одинаковое число очков. Например, \(S6\), \(D3\) и \(T2\) дают по \(6\) очков, но это разные попадания, и перед финальным броском их нельзя склеивать в один вариант. Следовательно, считать нужно именованные области, а не только числовые суммы.
Обозначим через \(A\) множество всех допустимых нефинальных бросков, а через \(F\) - множество всех допустимых завершающих бросков. Тогда
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
и
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
Если \(v(x)\) обозначает число очков, которое приносит сектор \(x\), то вся задача сводится к конечному комбинаторному подсчёту на этих двух множествах.
Фиксированное место в порядке имеет только последний бросок. Первые два броска можно переставить, и новый чекаут при этом не возникает. Поэтому начальную часть удобнее всего моделировать как мультимножество размера \(0\), \(1\) или \(2\), выбранное из \(A\). Размер \(0\) соответствует чекауту из одного броска, размер \(1\) - из двух бросков, размер \(2\) - из трёх.
Эта же модель объясняет, почему в реализациях не нужны промахи. Более короткий чекаут уже описывается выбором меньшего числа предварительных бросков, так что явное добавление misses только продублировало бы существующие случаи.
Пусть \(A=\{a_1,\dots,a_{62}\}\). Тогда для порога \(L\) каждый допустимый чекаут считается ровно один раз формулой
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
Здесь \(\mathbf{1}(\cdot)\) - индикатор: он равен \(1\), когда неравенство выполняется, и \(0\) иначе. Условие \(i\le j\) и есть математическая форма правила «первые два броска неупорядочены, но повторения, например \(\{D1,D1\}\), разрешены».
Если пока забыть про ограничение \(L=100\), общее число формальных шаблонов чекаута считается сразу. Есть \(21\) завершение одним броском, \(62\cdot 21\) завершений двумя бросками и
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
завершений тремя бросками, потому что первые два броска образуют двухэлементное мультимножество из \(62\) типов областей. Значит, полный нефильтрованный поиск содержит
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
различных формальных чекаутов. Задача Project Euler просит лишь подмножество с суммой меньше \(100\).
Полезная проверка - случай \(L=6\). Завершающими даблами здесь могут быть только \(D1\) и \(D2\), потому что \(D3=6\) уже не удовлетворяет строгому неравенству.
Если чекаут заканчивается на \(D1\), то сумма предварительных бросков должна быть меньше \(4\). Это даёт одно пустое мультимножество, пять вариантов из одного броска \((S1,S2,D1,S3,T1)\) и три мультимножества из двух бросков: \(\{S1,S1\}\), \(\{S1,S2\}\) и \(\{S1,D1\}\). Значит, окончания на \(D1\) дают \(1+5+3=9\) чекаутов.
Если чекаут заканчивается на \(D2\), предварительная сумма должна быть меньше \(2\). Возможны только пустое мультимножество и одиночный бросок \(S1\), так что добавляются ещё \(2\) чекаута. Следовательно,
$$C(6)=9+2=11.$$
Этот пример одновременно показывает важный инвариант: совпадение числового счёта не склеивает разные сектора. \(S3\) и \(T1\) оба дают \(3\), но после \(D1\) это всё равно два разных чекаута.
Реализации на C++, Python и Java сначала строят две таблицы, которые прямо соответствуют математической модели: \(62\) допустимые нефинальные области и \(21\) допустимый завершающий дабл. Для каждого элемента хранится и метка, и числовое значение, поэтому дальше всё сводится к простым сложениям и сравнениям.
Затем выполняются три прохода подсчёта, соответствующие трём слагаемым формулы. Первый считает чекауты из одного броска. Второй перебирает каждую нефинальную область вместе с каждым завершающим даблом. Третий рассматривает два предварительных броска как неупорядоченную пару: второй индекс начинается с текущей позиции первого, поэтому повторения сохраняются, а перестановка первых двух бросков не приводит к двойному счёту.
Каждый кандидат принимается тогда и только тогда, когда его суммарный счёт строго меньше заданного предела. В реализации на C++ этот предел параметризован и дополнительно проверяется малый случай \(L=6\); реализации на Python и Java вычисляют ту же самую схему сразу для \(L=100\).
Пространство кандидатов очень мало. Имеется \(21\) вариант из одного броска, \(62\cdot 21=1302\) варианта из двух бросков и \(\binom{63}{2}\cdot 21=41013\) вариантов из трёх бросков, то есть всего \(42336\) кандидатов до фильтрации. Поэтому прямой перебор здесь не просто допустим, а является естественным точным методом.
В обобщённой записи время работы равно \(O(|F|\cdot |A|^2)\), поскольку доминирует обход неупорядоченных пар первых бросков. Память составляет \(O(|A|+|F|)\) для двух списков областей; для фиксированной доски это, по сути, константа.
في هذه المسألة الخاصة بالسهام يمكن أن يتكوّن الـ checkout من سهم واحد أو سهمين أو ثلاثة، لكن السهم الأخير يجب أن يكون في خانة double. المطلوب هو عدّ جميع طرق الإنهاء المختلفة التي يكون مجموع نقاطها أقل من \(100\) على نحو صارم.
الكلمة الحاسمة هنا هي مختلفة. فالمواضع المختلفة على اللوح تُعدّ منفصلة حتى لو أعطت القيمة العددية نفسها. على سبيل المثال \(S6\) و\(D3\) و\(T2\) كلها تعطي \(6\) نقاط، لكنها تمثل إصابات مختلفة، ولذلك يجب عدّها بشكل مستقل عندما تظهر قبل السهم الأخير. إذن العدّ الصحيح يكون على مستوى المناطق المسماة لا على مستوى المجموعات العددية فقط.
لنرمز بـ \(A\) إلى مجموعة جميع الرميات المسموح بها قبل السهم الأخير، وبـ \(F\) إلى مجموعة الرميات المسموح بها في النهاية. عندئذ
$$A=\{S1,\dots,S20,D1,\dots,D20,T1,\dots,T20,S25,D25\},\qquad |A|=62,$$
و
$$F=\{D1,\dots,D20,D25\},\qquad |F|=21.$$
إذا رمزنا لقيمة المنطقة \(x\) بالرمز \(v(x)\)، فإن المسألة كلها تتحول إلى مسألة عدّ منتهية على هاتين المجموعتين.
الرمية الوحيدة التي تحتفظ بموضعها المميز في الترتيب هي الرمية الأخيرة. أما الرميتان الأوليان فيمكن تبديلهما من دون أن نحصل على checkout جديد. لذلك فإن أفضل نموذج رياضي هو اعتبار الجزء التمهيدي multiset حجمه \(0\) أو \(1\) أو \(2\) مأخوذًا من \(A\). فالحجم \(0\) يمثل إنهاءً بسهم واحد، والحجم \(1\) يمثل إنهاءً بسهمين، والحجم \(2\) يمثل إنهاءً بثلاثة أسهم.
ومن هنا نفهم أيضًا لماذا لا تظهر رمية miss صراحةً في التنفيذ. فطريقة الإنهاء الأقصر ممثلة أصلًا باختيار عدد أقل من الرميات التمهيدية، وإضافة misses ككائنات مستقلة لن تنتج حالات جديدة بل ستكرر حالات موجودة.
اكتب \(A=\{a_1,\dots,a_{62}\}\). ولأي حد \(L\)، يمكن عدّ كل checkout صحيح مرة واحدة تمامًا بواسطة الصيغة
$$C(L)=\sum_{d\in F}\mathbf{1}\bigl(v(d)\lt L\bigr)+\sum_{i=1}^{62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(d)\lt L\bigr)+\sum_{1\le i\le j\le 62}\sum_{d\in F}\mathbf{1}\bigl(v(a_i)+v(a_j)+v(d)\lt L\bigr).$$
هنا \(\mathbf{1}(\cdot)\) هي دالة المؤشر: تعطي \(1\) عندما يتحقق الشرط و\(0\) خلاف ذلك. أما الشرط \(i\le j\) فهو الصياغة الرياضية لعبارة: “الرميتان الأوليان غير مرتبتين، لكن التكرار مثل \(\{D1,D1\}\) ما زال مسموحًا”.
قبل فرض القيد \(L=100\)، يمكن حساب عدد أنماط الإنهاء الشكلية مباشرةً. لدينا \(21\) حالة إنهاء بسهم واحد، و\(62\cdot 21\) حالة إنهاء بسهمين، و
$$\binom{62+1}{2}\cdot 21=\binom{63}{2}\cdot 21$$
حالة إنهاء بثلاثة أسهم، لأن الرميتين الأوليين تشكلان multiset من عنصرين مختارًا من \(62\) نوعًا من المناطق. لذلك فإن فضاء البحث غير المقيّد يحتوي على
$$21+62\cdot 21+\binom{63}{2}\cdot 21=42336$$
checkout شكليًا مختلفًا. أما المسألة الفعلية فتطلب فقط الجزء الذي يكون مجموعه أقل من \(100\).
من المفيد استخدام \(L=6\) كاختبار سلامة. في هذه الحالة لا يمكن أن تكون الرمية الأخيرة إلا \(D1\) أو \(D2\)، لأن \(D3=6\) لا يحقق شرط الأصغر الصارم.
إذا انتهى الـ checkout بـ \(D1\)، فيجب أن يكون مجموع الرميات السابقة أقل من \(4\). وهذا يعطي multiset فارغًا واحدًا، وخمس خيارات أحادية \((S1,S2,D1,S3,T1)\)، وثلاثة multisets ثنائية هي \(\{S1,S1\}\) و\(\{S1,S2\}\) و\(\{S1,D1\}\). إذن النهايات التي تنتهي بـ \(D1\) تساهم بعدد \(1+5+3=9\) من الـ checkouts.
أما إذا انتهى الـ checkout بـ \(D2\)، فيجب أن يكون مجموع الجزء التمهيدي أقل من \(2\). ولا يوجد هنا إلا multiset الفارغ والرميـة الوحيدة \(S1\)، أي \(2\) checkouts إضافية. وبالتالي
$$C(6)=9+2=11.$$
ويُظهر هذا المثال أيضًا ثابتًا مهمًا: تساوي النقاط لا يدمج المناطق المختلفة. فـ \(S3\) و\(T1\) يعطيان كل منهما \(3\) نقاط، لكنهما يبقيان checkouts مختلفين عندما يتبعهما \(D1\).
تبدأ تطبيقات C++ وPython وJava ببناء القائمتين المطابقتين تمامًا للنموذج الرياضي: \(62\) منطقة مسموح بها قبل السهم الأخير، و\(21\) double مسموحًا به في الإنهاء. وكل عنصر يحتفظ باسمه وقيمته العددية معًا، لذلك تصبح المراحل اللاحقة مجرد عمليات جمع ومقارنة.
بعد ذلك تنفّذ ثلاثة مروريات عدّ، وكل مرور يطابق حدًا من حدود الصيغة السابقة. الأول يعدّ الإنهاءات ذات السهم الواحد. والثاني يزاوج كل منطقة تمهيدية مع كل double نهائي. أما الثالث فيعدّ الرميتين التمهيديتين كزوج غير مرتب، وذلك بجعل الحلقة الثانية تبدأ من الموضع الحالي للحلقة الأولى؛ وهكذا تبقى التكرارات ممكنة، لكن تبديل ترتيب الرميتين لا يؤدي إلى عدّ مزدوج.
يُقبل كل نمط مرشح إذا وفقط إذا كان مجموع نقاطه أقل من الحد المطلوب. تطبيق C++ يجعل هذا الحد معاملًا عامًا ويختبر الحالة الصغيرة \(L=6\)، بينما تطبّق نسختا Python وJava العدّ نفسه مباشرةً عند \(L=100\).
فضاء المرشحين صغير جدًا. هناك \(21\) حالة بسهم واحد، و\(62\cdot 21=1302\) حالة بسهمين، و\(\binom{63}{2}\cdot 21=41013\) حالة بثلاثة أسهم، أي \(42336\) مرشحًا فقط قبل التصفية. لهذا السبب فإن التعداد المباشر ليس ممكنًا فحسب، بل هو الطريقة الدقيقة الطبيعية لهذه المسألة.
بصياغة عامة يكون زمن التنفيذ \(O(|F|\cdot |A|^2)\)، لأن المرور على الأزواج غير المرتبة للرميتين التمهيديتين هو الجزء المسيطر. أما الذاكرة فهي \(O(|A|+|F|)\) لتخزين القائمتين، وهو مقدار ثابت عمليًا بالنسبة إلى لوحة اللعبة الثابتة هنا.