A positive integer is called reachable if it can be obtained from the digits
1,2,3,4,5,6,7,8,9
used in this exact order and exactly once each, under the following rules:
1. Between two consecutive digits we may place one of the four binary operations +, -, *, /, or we may concatenate the digits.
2. Parentheses may be inserted arbitrarily.
3. Unary minus is not allowed.
The goal is to find the sum of all distinct positive integers that are reachable exactly.
There are 8 gaps between the 9 digits. In each gap we choose one symbol from
$$\{+,-,\times,\div,\#\},$$
where \(\#\) means decimal concatenation.
Therefore the total number of raw operator patterns is
$$5^8=390625.$$
For example, the pattern
1#2 + 3#4 * 5 - 6#7#8 / 9
collapses to the token list
$$12,\ 34,\ 5,\ 678,\ 9$$
with operator list
$$+,\ \times,\ -,\ \div.$$
So after concatenations are resolved, every pattern becomes a sequence
$$v_0,v_1,\dots,v_{m-1}\in \mathbb Z_{>0}$$
together with operators
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
where \(1\le m\le 9\).
Once the token list is fixed, the only remaining freedom is the parenthesization.
Any fully parenthesized binary expression over
$$v_l,v_{l+1},\dots,v_r$$
has a last operation performed at some split position \(k\), where
$$l\le k<r.$$
That last step combines:
1. a fully parenthesized expression on the left interval \([l,k]\),
2. a fully parenthesized expression on the right interval \([k+1,r]\),
3. the fixed operator \(o_k\) between those two intervals.
This is exactly the same structural idea as matrix-chain dynamic programming: every binary tree has a final split.
For every interval \([l,r]\), define
$$R_{l,r}=\{\text{all exact rational values obtainable from }v_l,\dots,v_r\}.$$
The base case is immediate:
$$R_{i,i}=\{v_i\}.$$
For longer intervals, we split at every possible \(k\):
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
The only forbidden operation is division by zero, so in the division case we keep only pairs with
$$b\ne 0.$$
This recurrence covers every legal parenthesization exactly because every binary expression tree has one unique last split.
Intermediate values do not have to be integers. In fact, some reachable positive integers can only be built by passing through fractions.
The official statement gives the example
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
Indeed,
$$((4\times 5)-6)=14,\qquad (78-9)=69,$$
so the expression becomes
$$\frac{1}{23}\times 14\times 69=\frac{966}{23}=42.$$
If we stored only integers, or if we used floating-point approximations, we would lose valid results. Therefore the solver stores every intermediate value as an exact reduced rational number.
Consider the short token list
$$1,\ 2,\ 3$$
with operators
$$+,\ \times.$$
Then
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
For the interval \([0,1]\), we get
$$R_{0,1}=\{1+2\}=\{3\}.$$
For \([1,2]\),
$$R_{1,2}=\{2\times 3\}=\{6\}.$$
Finally, interval \([0,2]\) has two splits:
$$((1+2)\times 3)=9,$$
$$1+(2\times 3)=7.$$
Hence
$$R_{0,2}=\{7,9\}.$$
This small example shows exactly why a single left-to-right evaluation is not enough: different parenthesizations genuinely create different results.
Different splits can lead to the same rational number. Also, the same result can appear through different parenthesizations. So every \(R_{l,r}\) must be stored as a set of unique exact values.
The code uses reduced fractions, so for example
$$\frac12=\frac24$$
is recognized automatically as one value, not two.
This local deduplication is important because otherwise the number of intermediate objects would explode much faster.
The DP for one token pattern returns every reachable rational number for the full interval \([0,m-1]\).
A result contributes to the final answer if and only if:
1. its denominator is 1,
2. its numerator is positive.
So the acceptance condition is exactly
$$q=1\qquad\text{and}\qquad p>0$$
for a reduced fraction \(p/q\).
All such integers from all 390625 patterns are inserted into one global set, and only then are they summed. This prevents counting the same reachable integer more than once when it arises from different operator patterns.
Concatenation is not a binary arithmetic operation on two already-evaluated subexpressions. It is a lexical operation on adjacent digits before the arithmetic tree is built.
That is why the code first converts each base-5 pattern into a token list of integers. Only after this preprocessing step does the interval DP begin.
Mathematically, this separates the problem into two layers:
1. choose how digits are grouped into decimal numbers,
2. choose how those numbers are combined by arithmetic and parentheses.
If a token pattern has \(m\) numbers, then the number of full binary parenthesizations is the Catalan number
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
In the worst case \(m=9\), this gives
$$C_8=1430.$$
The DP does not explicitly generate these 1430 trees one by one. Instead, it memoizes interval results, so every interval is solved once and then reused wherever needed.
The function collect_for_range processes a block of pattern codes. Each pattern code is read in base 5, which tells the program what to place in each of the 8 gaps.
After tokenization, all_results performs the interval DP and returns all exact reachable rationals for that pattern.
Each thread keeps a local vector of positive integers found in its assigned range. Those vectors are sorted and deduplicated locally, then merged globally at the end.
The final sum uses cpp_int rather than 64-bit integers, because the total sum of all reachable positive integers is too large to assume a small fixed machine type.
The 390625 patterns are completely independent. No pattern needs information from another. So the full search space can be split into disjoint ranges and processed in parallel without changing the mathematical result.
Each worker computes exact reachable values for its own code range, deduplicates locally, and the main thread performs one final union.
The helper op_from_code converts base-5 digits into one of the five gap choices. The function collect_for_range decodes a pattern, resolves concatenations into a vector of integers values, and builds the matching operator list ops.
The function all_results(values, ops) allocates a 2D DP table where entry \([l][r]\) stores every exact fraction reachable on that token interval. For each split \(k\), it combines every left value with every right value using operator ops[k], skipping division by zero, and deduplicates with a set.
After all threads finish, the main routine merges their integer outputs, removes duplicates once more globally, and sums the remaining values with arbitrary-precision integer arithmetic.
The total number of token patterns is fixed at
$$5^8=390625.$$
For one pattern with \(m\) numeric tokens, interval DP has
$$O(m^2)$$
subintervals and up to
$$O(m)$$
split points per interval. The real cost is dominated by the sizes of the intermediate rational sets and the cartesian products formed when combining them.
Since \(m\le 9\), the token dimension is very small; what makes the problem nontrivial is the huge number of patterns and the need for exact deduplication. Memory usage is proportional to the total number of fractions stored across all DP intervals for one pattern, plus the thread-local and global sets of reachable integers.
Eine positive ganze Zahl heißt erreichbar, wenn sie aus den Ziffern
1,2,3,4,5,6,7,8,9
in genau dieser Reihenfolge und jeweils genau einmal gebildet werden kann, wobei zwischen zwei benachbarten Ziffern entweder +, -, *, / oder Konkatenation eingesetzt wird. Klammern dürfen beliebig gesetzt werden, ein unärer Minusoperator ist jedoch nicht erlaubt.
Gesucht ist die Summe aller verschiedenen positiven ganzen Zahlen, die sich auf diese Weise exakt erzeugen lassen.
Zwischen den 9 Ziffern gibt es genau 8 Lücken. In jede Lücke kommt eine Wahl aus
$$\{+,-,\times,\div,\#\},$$
wobei \(\#\) die Dezimalkonkatenation bezeichnet.
Damit gibt es insgesamt
$$5^8=390625$$
rohe Muster.
Nach dem Auflösen aller Konkatenationen erhält man eine Zahlenfolge
$$v_0,v_1,\dots,v_{m-1}$$
und eine Operatorkette
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
wobei \(1\le m\le 9\).
Ist die Tokenfolge fest, bleibt nur noch die Klammerung frei. Jede vollständig geklammerte binäre Auswertung auf einem Intervall \([l,r]\) besitzt einen letzten Rechenschritt an einer eindeutigen Split-Position \(k\) mit
$$l\le k<r.$$
Dieser letzte Schritt kombiniert:
1. einen Wert aus dem linken Intervall \([l,k]\),
2. einen Wert aus dem rechten Intervall \([k+1,r]\),
3. den festen Operator \(o_k\) dazwischen.
Genau daraus entsteht die Intervall-DP.
Für jedes Intervall definieren wir
$$R_{l,r}=\{\text{alle exakten rationalen Werte aus }v_l,\dots,v_r\}.$$
Die Basis lautet
$$R_{i,i}=\{v_i\}.$$
Für längere Intervalle gilt
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
Im Divisionsfall werden nur Paare mit
$$b\ne 0$$
zugelassen.
Zwischenwerte müssen nicht ganzzahlig sein. Manche erreichbaren positiven ganzen Zahlen entstehen erst über Zwischenbrüche.
Das offizielle Beispiel ist
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
Hier treten also sowohl Konkatenation als auch echte Brüche auf. Deshalb speichert der Solver alle Zwischenwerte als vollständig gekürzte rationale Zahlen und nicht als Gleitkommazahlen.
Betrachte die Tokenfolge
$$1,\ 2,\ 3$$
mit Operatoren
$$+,\ \times.$$
Dann gilt
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
Für \([0,1]\) erhält man
$$R_{0,1}=\{3\},$$
für \([1,2]\) erhält man
$$R_{1,2}=\{6\}.$$
Beim Gesamtintervall \([0,2]\) gibt es zwei Klammerungen:
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
Also
$$R_{0,2}=\{7,9\}.$$
Verschiedene Splits oder verschiedene Klammerungen können denselben rationalen Wert erzeugen. Deshalb muss jedes \(R_{l,r}\) als Menge eindeutiger Werte gespeichert werden.
Da die Brüche gekürzt gespeichert werden, erkennt das Programm etwa
$$\frac12=\frac24$$
automatisch als denselben Wert.
Ein Ergebnis trägt nur dann zur globalen Summe bei, wenn es ein positiver ganzzahliger Wert ist. Für einen gekürzten Bruch \(p/q\) bedeutet das exakt:
$$q=1\qquad\text{und}\qquad p>0.$$
Alle solchen Werte aus allen 390625 Mustern werden global vereinigt und erst danach einmal summiert.
Konkatenation ist keine gewöhnliche binäre Rechenoperation auf bereits ausgewerteten Teilbäumen. Sie ist ein lexikalischer Schritt auf benachbarten Ziffern. Darum löst der Code zuerst alle \(\#\)-Marker auf und baut daraus die Tokenliste auf. Erst danach beginnt die eigentliche arithmetische Intervall-DP.
Hat ein Muster \(m\) Zahlen-Tokens, dann ist die Zahl aller vollständigen binären Klammerungen die Catalan-Zahl
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
Im schlimmsten Fall \(m=9\) ist das
$$C_8=1430.$$
Die DP erzeugt diese Bäume nicht einzeln, sondern memoisiert Intervallresultate und benutzt sie wieder.
collect_for_range verarbeitet einen Bereich von Muster-Codes. Jeder Code wird in Basis 5 gelesen und dadurch in die 8 Lückenentscheidungen zerlegt.
Nach der Tokenisierung berechnet all_results per Intervall-DP alle exakten rationalen Werte für dieses Muster.
Jeder Thread sammelt seine lokal gefundenen positiven ganzen Zahlen, sortiert und dedupliziert lokal, und erst am Ende erfolgt die globale Vereinigung. Die Endsumme wird mit cpp_int gebildet, weil die Gesamtantwort bewusst nicht als kleiner 64-Bit-Wert angenommen wird.
op_from_code wandelt Basis-5-Ziffern in Operatoren um. collect_for_range löst daraus Konkatenationen auf und erzeugt die Vektoren values und ops.
all_results(values, ops) baut die 2D-DP-Tabelle auf. Für jedes Intervall und jede Split-Stelle kombiniert die Funktion alle linken und rechten Werte mit dem passenden Operator, überspringt Division durch null und dedupliziert mit einer Menge.
Nach Abschluss aller Threads werden die lokalen Ergebnisvektoren zusammengeführt, global dedupliziert und mit beliebig großer Ganzzahlarithmetik aufsummiert.
Die Zahl der Rohmuster ist fest:
$$5^8=390625.$$
Für ein einzelnes Muster mit \(m\) Tokens besitzt die Intervall-DP
$$O(m^2)$$
Teilintervalle und bis zu
$$O(m)$$
Splitstellen je Intervall. Die eigentliche Laufzeit wird jedoch vor allem durch die Größen der Zwischenmengen rationaler Werte bestimmt. Da \(m\le 9\), ist die Token-Dimension klein; anspruchsvoll ist vor allem die große Zahl von Mustern und die exakte Deduplikation.
Bir pozitif tam sayı, aşağıdaki kurallara uyan bir aritmetik ifadeden elde edilebiliyorsa reachable sayılır:
1. Rakamlar 1,2,3,4,5,6,7,8,9 tam bu sırayla ve tam birer kez kullanılmalıdır.
2. Ardışık iki rakam arasına +, -, *, / veya birleştirme konabilir.
3. Parantezler istenildiği gibi yerleştirilebilir.
4. Tekli eksi yasaktır.
Amaç, ulaşılabilen tüm farklı pozitif tam sayıların toplamını bulmaktır.
9 rakam arasında tam 8 boşluk vardır. Her boşluk için
$$\{+,-,\times,\div,\#\}$$
kümesinden bir seçim yapılır; burada \(\#\) ondalık birleştirme demektir.
Bu yüzden toplam ham desen sayısı
$$5^8=390625$$
olur.
Birleştirmeler çözüldüğünde, her desen şu biçime dönüşür:
$$v_0,v_1,\dots,v_{m-1}\in\mathbb Z_{>0}$$
ve bunların arasındaki işlem listesi
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\}.$$
Burada \(1\le m\le 9\) olur.
Token listesi sabitlendiğinde geriye yalnızca parantezleme serbestliği kalır.
\([l,r]\) aralığındaki herhangi bir tam parantezli ifade, son adımında mutlaka bir \(k\) bölme noktasında iki alt ifadeyi birleştirir:
$$l\le k<r.$$
Bu son adımda:
1. soldan \([l,k]\) aralığındaki bir değer,
2. sağdan \([k+1,r]\) aralığındaki bir değer,
3. aradaki sabit operatör \(o_k\)
kullanılır. Bu yüzden doğal yapı interval dynamic programming olur.
Her \([l,r]\) aralığı için
$$R_{l,r}=\{\text{\(v_l,\dots,v_r\) kullanılarak elde edilebilen tüm tam rasyonel değerler}\}$$
tanımlanır.
Başlangıç durumu:
$$R_{i,i}=\{v_i\}.$$
Geçiş:
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
Bölme işleminde yalnızca
$$b\ne 0$$
olan durumlar tutulur.
Ara değerlerin tam sayı olması gerekmez. Hatta bazı reachable tam sayılar ancak kesirlerden geçerek elde edilir.
Resmî problemde verilen örnek şudur:
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
Burada hem birleştirme hem de ara kesirler vardır. Dolayısıyla kayan noktalı sayı kullanmak doğru olmaz; her ara değer indirgenmiş rasyonel sayı olarak tutulmalıdır.
Şu kısa token listesini düşünelim:
$$1,\ 2,\ 3$$
ve işlemler
$$+,\ \times.$$
O zaman
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
\([0,1]\) aralığı için
$$R_{0,1}=\{3\},$$
\([1,2]\) aralığı için
$$R_{1,2}=\{6\}$$
elde edilir.
Toplam aralık \([0,2]\) ise iki farklı son bölmeye sahiptir:
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
Dolayısıyla
$$R_{0,2}=\{7,9\}.$$
Bu örnek, tek bir soldan sağa değerlendirme yerine tüm ikili parantez ağaçlarının neden hesaba katılması gerektiğini gösterir.
Farklı bölme noktaları veya farklı parantezlemeler aynı rasyonel değeri üretebilir. Bu nedenle her \(R_{l,r}\) küme mantığıyla tutulmalıdır.
Kesirler indirgenmiş biçimde saklandığı için örneğin
$$\frac12=\frac24$$
otomatik olarak tek değer kabul edilir.
Bir desen için tüm ifade sonuçları bulunduğunda, bir değerin genel cevaba katkı yapması için şunlar gerekir:
1. payda 1 olmalı,
2. pay pozitif olmalı.
Yani indirgenmiş \(p/q\) kesri için koşul tam olarak
$$q=1\qquad\text{ve}\qquad p>0$$
şeklindedir.
Tüm 390625 desenden gelen bu tür tamsayılar tek bir global kümede birleştirilir ve ancak sonra toplanır. Böylece aynı tam sayı farklı desenlerden gelse bile yalnızca bir kez sayılır.
Birleştirme, iki hazır alt ifadenin üzerine uygulanan sıradan bir ikili işlem değildir. O, önce komşu rakamları tek bir ondalık sayıya dönüştüren sözdizimsel bir adımdır.
Bu yüzden kod önce \(\#\) işaretlerini çözerek token listesini kurar; asıl aritmetik interval DP bundan sonra başlar.
Bir desende \(m\) adet sayı token'ı varsa, tam ikili parantezleme sayısı Catalan sayısıdır:
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
En kötü durumda \(m=9\) için
$$C_8=1430$$
olur.
DP, bu 1430 ağacı tek tek üretmez; aynı interval sonuçlarını belleğe alıp tekrar kullanır.
collect_for_range belli bir kod aralığını işler. Her kod taban-5 olarak çözülür ve 8 boşluğun her biri için hangi seçim yapıldığı bulunur.
Tokenizasyon sonrası all_results çağrılır ve bu desen için ulaşılabilen tüm tam rasyonel değerler hesaplanır.
Her iş parçacığı kendi aralığından bulduğu pozitif tamsayıları yerel vektörde toplar, yerel sıralama ve tekilleştirme yapar. Ana iş parçacığı ise en sonunda bunları birleştirir.
Nihai toplam için cpp_int kullanılır; çünkü reachable tamsayıların toplamı küçük bir 64-bit türüne güvenilecek kadar sınırlı kabul edilmez.
390625 desen birbirinden tamamen bağımsızdır. Bir desenin sonucu başka bir desene bağlı değildir. Bu yüzden aralıklar güvenli biçimde parçalara ayrılıp paralel işlenebilir. Son matematiksel sonuç, yalnızca en sonda yapılan birleşim ve tekilleştirmedir.
op_from_code taban-5 rakamlarını operatörlere çevirir. collect_for_range bu desenleri okuyup önce birleştirmeleri çözer, sonra values ve ops listelerini üretir.
all_results(values, ops), \([l][r]\) girişlerinde o intervalde elde edilebilen tüm kesirleri tutan bir 2B DP tablosu kurar. Her bölme noktası için soldaki ve sağdaki tüm sonuçlar uygun operatörle birleştirilir, sıfıra bölme atlanır ve sonuçlar kümeyle tekilleştirilir.
Tüm iş parçacıkları bittikten sonra ana yordam yerel sonuçları birleştirir, global tekilleştirme yapar ve geriye kalan pozitif tamsayıları büyük tam sayı aritmetiğiyle toplar.
Toplam ham desen sayısı sabittir:
$$5^8=390625.$$
Bir desen için, \(m\) token üzerinde interval DP'nin
$$O(m^2)$$
adet alt aralığı ve aralık başına en fazla
$$O(m)$$
bölme noktası vardır. Gerçek maliyet ise esas olarak ara rasyonel kümelerin boyutlarına ve bunların kartezyen çarpımlarına bağlıdır.
\(m\le 9\) olduğu için token boyutu küçüktür; asıl zorluk çok sayıdaki desen ve tam doğrulukla tekilleştirme yapmaktır. Bellek tüketimi, tek bir desen için tüm interval kümelerinde saklanan kesir sayısına ve thread-local / global sonuç kümelerine bağlıdır.
Un entero positivo se llama alcanzable si puede obtenerse a partir de los digitos
1,2,3,4,5,6,7,8,9
usados exactamente una vez y en ese mismo orden, bajo estas reglas:
1. En cada hueco se puede poner +, -, *, / o concatenacion.
2. Los parentesis pueden colocarse libremente.
3. No se permite menos unario.
La meta es sumar todos los enteros positivos distintos que sean alcanzables exactamente.
Hay 8 huecos entre 9 digitos. En cada uno elegimos un simbolo de
$$\{+,-,\times,\div,\#\},$$
donde \(\#\) significa concatenacion decimal.
Por tanto, el numero total de patrones brutos es
$$5^8=390625.$$
Al resolver las concatenaciones, cada patron se convierte en una lista de numeros
$$v_0,v_1,\dots,v_{m-1}$$
y una lista de operadores
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
con \(1\le m\le 9\).
Una vez fijada la lista de tokens, la unica libertad restante es la parentizacion.
Cualquier expresion binaria completamente parentizada sobre el intervalo \([l,r]\) tiene una ultima operacion en algun punto de corte \(k\) con
$$l\le k<r.$$
Esa ultima operacion combina:
1. un resultado del intervalo izquierdo \([l,k]\),
2. un resultado del intervalo derecho \([k+1,r]\),
3. el operador fijo \(o_k\).
Definimos
$$R_{l,r}=\{\text{todos los valores racionales exactos obtenibles con }v_l,\dots,v_r\}.$$
Base:
$$R_{i,i}=\{v_i\}.$$
Transicion:
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
En el caso de division solo se aceptan parejas con
$$b\ne 0.$$
Los valores intermedios no tienen por que ser enteros. Algunas soluciones enteras pasan necesariamente por fracciones.
El ejemplo oficial es
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
Por eso el algoritmo guarda cada valor intermedio como racional exacto reducido y no como numero en coma flotante.
Tomemos la lista de tokens
$$1,\ 2,\ 3$$
con operadores
$$+,\ \times.$$
Entonces
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
Para \([0,1]\),
$$R_{0,1}=\{3\},$$
y para \([1,2]\),
$$R_{1,2}=\{6\}.$$
En el intervalo completo aparecen dos parentizaciones:
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
Por tanto
$$R_{0,2}=\{7,9\}.$$
Distintos cortes pueden llevar al mismo valor racional, y distintas parentizaciones tambien. Por eso cada \(R_{l,r}\) debe almacenarse como conjunto de valores unicos.
Como las fracciones se guardan reducidas, por ejemplo
$$\frac12=\frac24$$
se reconoce automaticamente como el mismo valor.
Un resultado cuenta solo si es un entero positivo. Para una fraccion reducida \(p/q\), eso equivale a
$$q=1\qquad\text{y}\qquad p>0.$$
Todos esos enteros, procedentes de los 390625 patrones, se unen en un conjunto global antes de sumarse, de modo que cada entero alcanzable se cuenta una sola vez.
La concatenacion no es una operacion aritmetica binaria sobre dos subexpresiones ya evaluadas. Es un paso sintactico sobre digitos consecutivos. Por eso el programa primero agrupa digitos en numeros decimales y solo despues ejecuta la DP aritmetica.
Si un patron tiene \(m\) tokens numericos, el numero de parentizaciones binarias completas es el numero de Catalan
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
En el peor caso \(m=9\), tenemos
$$C_8=1430.$$
La DP evita generar esos 1430 arboles uno por uno porque memoriza los resultados por intervalo.
collect_for_range procesa un bloque de codigos de patrones. Cada codigo se interpreta en base 5 y de ahi se obtienen las 8 decisiones de hueco.
Tras tokenizar, all_results calcula todos los racionales exactos alcanzables para ese patron.
Cada hilo mantiene un vector local con los enteros positivos encontrados en su rango, lo ordena y lo depura localmente. Al final el hilo principal hace la union global. La suma final se almacena en cpp_int.
op_from_code traduce digitos en base 5 a operadores. collect_for_range resuelve primero las concatenaciones y construye los vectores values y ops.
all_results(values, ops) crea la tabla DP por intervalos. Para cada corte \(k\), combina todos los resultados de la izquierda y de la derecha con el operador ops[k], omite la division por cero y elimina duplicados con un conjunto.
Cuando terminan todos los hilos, el programa fusiona sus salidas, vuelve a eliminar duplicados a nivel global y suma los enteros restantes con aritmetica de precision arbitraria.
El numero total de patrones es fijo:
$$5^8=390625.$$
Para un patron con \(m\) tokens, la DP por intervalos tiene
$$O(m^2)$$
subproblemas y hasta
$$O(m)$$
puntos de corte por subproblema. El coste real viene dominado por el tamano de los conjuntos intermedios de racionales y por sus combinaciones. Como \(m\le 9\), la dimension estructural es pequena; la dificultad real esta en los muchisimos patrones y en la deduplicacion exacta.
如果一个正整数可以由数字
1,2,3,4,5,6,7,8,9
按原顺序、各用一次，通过如下规则构造出来，就称它是 reachable：
1. 在相邻数字之间可以放 +、-、*、/ 或十进制拼接。
2. 括号可以任意放置。
3. 不允许一元负号。
目标是把所有不同的可达正整数求并集后再求和。
9 个数字之间有 8 个空隙。每个空隙都从
$$\{+,-,\times,\div,\#\}$$
中选一个符号，其中 \(\#\) 表示十进制拼接。
因此总模式数为
$$5^8=390625.$$
先处理完拼接之后，每个模式都会变成一个数列
$$v_0,v_1,\dots,v_{m-1}$$
和一个运算符序列
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
其中 \(1\le m\le 9\)。
一旦 token 序列固定，唯一剩下的自由度就是括号结构。
任意一个作用在区间 \([l,r]\) 上的完全二叉表达式，都有一个最后执行的运算，它发生在某个切分点 \(k\) 上，其中
$$l\le k<r.$$
这个最后一步会把：
1. 左区间 \([l,k]\) 的某个值，
2. 右区间 \([k+1,r]\) 的某个值，
3. 中间固定的运算符 \(o_k\)
组合起来。这正是区间 DP 的标准结构。
对每个区间 \([l,r]\)，定义
$$R_{l,r}=\{\text{由 }v_l,\dots,v_r\text{ 能精确得到的全部有理数值}\}.$$
边界条件为
$$R_{i,i}=\{v_i\}.$$
转移为
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
在除法情形下，只保留
$$b\ne 0$$
的组合。
中间结果不一定是整数。有些最终的正整数只能通过中间分数得到。
官方给出的例子是
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
因此算法不能只保留整数，也不能使用浮点近似，而必须把每个中间值存成约分后的精确有理数。
考虑 token 序列
$$1,\ 2,\ 3$$
以及运算符
$$+,\ \times.$$
则
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
对区间 \([0,1]\)，有
$$R_{0,1}=\{3\},$$
对区间 \([1,2]\)，有
$$R_{1,2}=\{6\}.$$
而整个区间 \([0,2]\) 有两种最后切分方式：
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
所以
$$R_{0,2}=\{7,9\}.$$
不同切分点、不同括号结构可能得到同一个有理数。因此每个 \(R_{l,r}\) 都必须是“唯一值集合”。
由于分数按最简形式保存，所以
$$\frac12=\frac24$$
会自动视为同一个值。
对一个完整模式来说，最终区间 \([0,m-1]\) 的结果中，只有满足以下条件的值才会贡献到总和：
1. 分母等于 1；
2. 分子为正。
也就是对最简分数 \(p/q\)，条件正是
$$q=1\qquad\text{且}\qquad p>0.$$
来自全部 390625 个模式的这些正整数会被放入一个全局集合，最终只加一次。
拼接不是“两个已算好的子表达式之间的普通二元运算”，而是先把相邻数字词法上合并成十进制整数。因此代码必须先消化所有 \(\#\)，得到 token 列表，然后才开始真正的算术区间 DP。
如果某个模式产生了 \(m\) 个数 token，那么其完整二叉括号结构数量就是 Catalan 数
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
最坏情况下 \(m=9\)，于是
$$C_8=1430.$$
代码并不把这 1430 棵树逐一生成，而是通过区间 DP 复用子区间结果。
collect_for_range 负责处理一段模式编号。每个编号按五进制展开，就得到 8 个空隙各自的选择。
完成 token 化之后，all_results 会求出该模式对应的全部精确有理数结果。
每个线程把自己范围内得到的正整数收集到局部向量中，先在本地排序去重，再由主线程做最终并集。总和使用 cpp_int 保存，以避免固定 64 位整数溢出。
op_from_code 把五进制数字映射为 5 种空隙选择。collect_for_range 先解析这些选择，解决拼接，再构造 values 和 ops 两个数组。
all_results(values, ops) 建立二维区间 DP 表。对每个切分点 \(k\)，它会把左区间和右区间的所有结果按 ops[k] 组合，跳过除零情况，并用集合去重。
所有线程结束后，主程序合并局部结果、再次全局去重，并用大整数把剩余正整数求和。
总模式数固定为
$$5^8=390625.$$
对一个含 \(m\) 个 token 的模式，区间 DP 有
$$O(m^2)$$
个子区间，每个子区间最多有
$$O(m)$$
个切分点。真正的开销主要来自中间有理数集合的大小以及左右集合做笛卡尔组合时的成本。
由于 \(m\le 9\)，结构尺寸本身不大；困难主要来自模式数量极多以及必须做精确去重。内存复杂度同样由这些中间集合和最终结果集合的大小主导。
Положительное целое число называется достижимым, если его можно получить из цифр
1,2,3,4,5,6,7,8,9
в этом же порядке и ровно по одному разу, соблюдая правила:
1. между соседними цифрами можно поставить +, -, *, / или конкатенацию;
2. скобки разрешены в любом виде;
3. унарный минус запрещен.
Нужно найти сумму всех различных положительных целых чисел, достижимых точно.
Между 9 цифрами есть ровно 8 промежутков. В каждый промежуток помещается один символ из
$$\{+,-,\times,\div,\#\},$$
где \(\#\) означает десятичную конкатенацию.
Итак, число сырых шаблонов равно
$$5^8=390625.$$
После выполнения всех конкатенаций каждый шаблон превращается в список чисел
$$v_0,v_1,\dots,v_{m-1}$$
и список операторов
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
где \(1\le m\le 9\).
Когда список токенов уже фиксирован, остается только свобода расстановки скобок.
Любое полностью скобочное бинарное выражение на интервале \([l,r]\) имеет последнюю операцию в некоторой точке разреза \(k\), где
$$l\le k<r.$$
Эта последняя операция объединяет:
1. значение из левого интервала \([l,k]\),
2. значение из правого интервала \([k+1,r]\),
3. фиксированный оператор \(o_k\).
Для каждого интервала определим
$$R_{l,r}=\{\text{все точные рациональные значения, достижимые из }v_l,\dots,v_r\}.$$
База:
$$R_{i,i}=\{v_i\}.$$
Переход:
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
В случае деления оставляются только пары с
$$b\ne 0.$$
Промежуточные значения вовсе не обязаны быть целыми. Некоторые итоговые положительные целые числа возникают только через промежуточные дроби.
Официальный пример:
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
Поэтому алгоритм обязан хранить промежуточные значения как точные сокращенные рациональные числа, а не как числа с плавающей точкой.
Рассмотрим токены
$$1,\ 2,\ 3$$
с операторами
$$+,\ \times.$$
Тогда
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
Для \([0,1]\) имеем
$$R_{0,1}=\{3\},$$
для \([1,2]\)
$$R_{1,2}=\{6\}.$$
На полном интервале \([0,2]\) существуют две скобочные структуры:
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
Поэтому
$$R_{0,2}=\{7,9\}.$$
Разные разрезы и разные скобочные структуры могут приводить к одному и тому же рациональному числу. Поэтому каждое множество \(R_{l,r}\) должно хранить только уникальные значения.
Поскольку дроби сокращаются, например
$$\frac12=\frac24$$
автоматически распознается как один и тот же результат.
Для сокращенной дроби \(p/q\) результат учитывается тогда и только тогда, когда
$$q=1\qquad\text{и}\qquad p>0.$$
То есть берутся только положительные целые значения. Все такие значения из всех 390625 шаблонов объединяются в одно глобальное множество и суммируются один раз.
Конкатенация не является обычной бинарной арифметической операцией над уже вычисленными поддеревьями. Это синтаксическая операция над соседними цифрами. Поэтому код сначала строит числовые токены, а уже потом запускает интервальную арифметическую DP.
Если в шаблоне получилось \(m\) числовых токенов, то число полных бинарных скобочных структур равно числу Каталана
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
В худшем случае \(m=9\), и тогда
$$C_8=1430.$$
DP не строит все 1430 деревьев по отдельности, а переиспользует результаты подинтервалов.
collect_for_range обрабатывает диапазон кодов шаблонов. Каждый код читается в системе счисления по основанию 5, что определяет 8 выборов между цифрами.
После токенизации функция all_results вычисляет все точные рациональные результаты для данного шаблона.
Каждый поток собирает свои положительные целые числа локально, сортирует и убирает дубли. Затем главный поток выполняет финальное объединение. Для суммы используется cpp_int.
op_from_code переводит цифру в базе 5 в один из пяти вариантов для промежутка. collect_for_range сперва разрешает конкатенации и строит списки values и ops.
all_results(values, ops) строит двумерную таблицу DP по интервалам. Для каждого разреза \(k\) она комбинирует все левые и правые значения через оператор ops[k], пропускает деление на ноль и убирает повторы с помощью множества.
После завершения всех потоков главный код сливает локальные результаты, снова устраняет глобальные дубли и суммирует итоговые положительные целые числа с использованием длинной арифметики.
Число шаблонов фиксировано:
$$5^8=390625.$$
Для одного шаблона с \(m\) токенами интервальная DP имеет
$$O(m^2)$$
подинтервалов и до
$$O(m)$$
точек разбиения. Основная стоимость определяется размерами промежуточных множеств рациональных значений и их попарными комбинациями. Так как \(m\le 9\), структурный размер мал, а основная трудность - огромное число шаблонов и точная дедупликация.
يُقال عن عدد صحيح موجب إنه reachable إذا أمكن الحصول عليه من الأرقام
1,2,3,4,5,6,7,8,9
مع استعمالها مرة واحدة لكل رقم وبالترتيب نفسه دائمًا، وفق القواعد التالية:
1. بين كل رقمين متجاورين يمكن وضع + أو - أو * أو / أو دمج عشري.
2. يمكن وضع الأقواس بأي شكل.
3. لا يُسمح بالناقص الأحادي.
المطلوب هو مجموع كل القيم الصحيحة الموجبة المختلفة التي يمكن الوصول إليها بدقة.
بين 9 أرقام توجد 8 فجوات. في كل فجوة نختار رمزًا من
$$\{+,-,\times,\div,\#\},$$
حيث ترمز \(\#\) إلى الدمج العشري.
إذًا فإن عدد الأنماط الخام يساوي
$$5^8=390625.$$
بعد حل جميع عمليات الدمج يتحول كل نمط إلى قائمة أعداد
$$v_0,v_1,\dots,v_{m-1}$$
وقائمة عمليات
$$o_0,o_1,\dots,o_{m-2}\in\{+,-,\times,\div\},$$
حيث \(1\le m\le 9\).
بعد تثبيت قائمة الرموز العددية، لا يبقى إلا حرية اختيار شكل الأقواس.
أي تعبير ثنائي كامل على المجال \([l,r]\) له عملية أخيرة واحدة تقع عند نقطة قطع \(k\) تحقق
$$l\le k<r.$$
وتقوم هذه العملية الأخيرة بدمج:
1. قيمة من المجال الأيسر \([l,k]\)،
2. قيمة من المجال الأيمن \([k+1,r]\)،
3. المعامل الثابت \(o_k\) بينهما.
لكل مجال \([l,r]\) نعرّف المجموعة \(R_{l,r}\) على أنها جميع القيم النسبية الدقيقة الممكنة الناتجة من \(v_l,\dots,v_r\).
حالة البداية هي
$$R_{i,i}=\{v_i\}.$$
أما الانتقال فهو
$$R_{l,r}=\bigcup_{k=l}^{r-1}\{a\;o_k\;b\mid a\in R_{l,k},\ b\in R_{k+1,r}\}.$$
وفي حالة القسمة لا نسمح إلا بالحالات التي فيها
$$b\ne 0.$$
القيم الوسيطة لا يلزم أن تكون أعدادًا صحيحة. بل إن بعض القيم الصحيحة النهائية لا يمكن الوصول إليها إلا عبر كسور وسيطة.
المثال الرسمي هو
$$(1/23)\times((4\times 5)-6)\times(78-9)=42.$$
لهذا السبب لا يكفي الاحتفاظ بالأعداد الصحيحة فقط، ولا يجوز استخدام التقريب العشري؛ بل يجب تخزين كل قيمة وسيطة على صورة كسر مختزل بدقة تامة.
لنأخذ قائمة الأعداد
$$1,\ 2,\ 3$$
ومعاملَي العمليات
$$+,\ \times.$$
عندئذٍ
$$R_{0,0}=\{1\},\qquad R_{1,1}=\{2\},\qquad R_{2,2}=\{3\}.$$
وبالنسبة إلى \([0,1]\) نحصل على
$$R_{0,1}=\{3\},$$
وبالنسبة إلى \([1,2]\) نحصل على
$$R_{1,2}=\{6\}.$$
أما المجال الكامل \([0,2]\) فيعطي شكلين مختلفين للأقواس:
$$((1+2)\times 3)=9,\qquad 1+(2\times 3)=7.$$
لذلك
$$R_{0,2}=\{7,9\}.$$
قد تؤدي نقاط القطع المختلفة أو أشكال الأقواس المختلفة إلى القيمة النسبية نفسها. لذلك يجب أن يُخزن كل \(R_{l,r}\) بوصفه مجموعة قيم فريدة.
وبما أن الكسور تحفظ في صورة مختزلة، فإن
$$\frac12=\frac24$$
يُنظر إليهما تلقائيًا على أنهما القيمة نفسها.
لكي تدخل قيمة ما في الجواب النهائي، يجب أن تكون عددًا صحيحًا موجبًا. وهذا يعني بالنسبة إلى الكسر المختزل \(p/q\) أن الشرط هو \(q=1\) و\(p>0\).
كل هذه القيم من جميع الأنماط 390625 تُجمع أولًا في مجموعة عامة واحدة، ثم تُحسب مرة واحدة فقط.
الدمج ليس عملية حسابية ثنائية عادية على تعبيرين جاهزين، بل هو خطوة تركيبية على الأرقام المتجاورة قبل بناء شجرة التعبير. لذلك يقوم الكود أولًا بتحويل سلاسل الأرقام المدموجة إلى أعداد عشرية، وبعد ذلك فقط يبدأ الـ interval DP الحسابي.
إذا احتوى نمط ما على \(m\) رموز عددية، فإن عدد جميع أشكال الأقواس الثنائية الكاملة هو عدد Catalan
$$C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}.$$
وفي أسوأ حالة حين \(m=9\)، نحصل على
$$C_8=1430.$$
لكن البرمجة الديناميكية لا تولد هذه الأشجار 1430 واحدةً واحدة، بل تعيد استخدام نتائج المجالات الفرعية.
تعالج الدالة collect_for_range مجالًا من أكواد الأنماط. ويُقرأ كل كود على أساس 5 للحصول على الاختيارات الثمانية بين الأرقام.
بعد التقطيع إلى أعداد وعمليات، تحسب all_results كل القيم النسبية الدقيقة الممكنة لذلك النمط.
كل خيط يجمع الأعداد الصحيحة الموجبة التي وجدها في متجه محلي، ويرتبها ويزيل تكرارها محليًا، ثم تنفذ الخيط الرئيسي عملية الاتحاد النهائية. ويُستخدم cpp_int لتخزين المجموع النهائي.
تحول op_from_code الرقم في النظام الخماسي إلى أحد خيارات الفجوة الخمسة. ثم تقوم collect_for_range بحل الدمج أولًا، وبعد ذلك تبني القائمتين values وops.
أما all_results(values, ops) فتبني جدول DP ثنائي الأبعاد على المجالات. ولكل نقطة قطع \(k\) تجمع كل القيم اليسرى مع كل القيم اليمنى باستخدام المعامل ops[k]، وتتجاوز القسمة على صفر، وتزيل التكرارات عبر مجموعة.
وبعد انتهاء جميع الخيوط، يدمج البرنامج النتائج المحلية، ويزيل التكرارات عالميًا مرة أخرى، ثم يجمع الأعداد الصحيحة الموجبة المتبقية باستعمال حساب صحيح كبير.
عدد الأنماط ثابت ويساوي
$$5^8=390625.$$
بالنسبة إلى نمط واحد يحوي \(m\) رموزًا عددية، فإن برمجة المجالات الديناميكية تملك
$$O(m^2)$$
مجالات فرعية، ولكل مجال حتى
$$O(m)$$
نقطة قطع. أما الكلفة الحقيقية فتتحكم فيها أحجام مجموعات الكسور الوسيطة وحجوم الضربات الديكارتية عند دمجها. وبما أن \(m\le 9\)، فالحجم البنيوي صغير، لكن عدد الأنماط الكبير وإزالة التكرارات بدقة هما مصدر الصعوبة الفعلية.