We begin at \((45,90)\) and may apply the two operations
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$$
A valid word is a finite string of \(r\) and \(s\) steps that reaches \(x=y\) at the end, but not at any earlier intermediate state. The implementation fixes counts \(R\) and \(S\) for the two operations, counts how many valid words exist for that pair, truncates the count to \(0\), \(1\), or \(\ge 2\), and then searches over total lengths \(m=R+S\). A preliminary unrestricted scan finds a 9-step equality at value \(1476\); the actual output scan then restricts to even lengths and returns the first even-length case with a unique valid word.
The core difficulty is that order matters: the two operations do not commute, and each later doubling amplifies earlier additive contributions. The program therefore combines exact recursion with a strong mathematical pruning rule.
Suppose we are currently at \((x,y)\) and still plan to use exactly \(R\) letters \(r\) and \(S\) letters \(s\). Every \(r\)-step adds \(1\) to \(x\), but that added \(1\) may later be doubled by some of the remaining \(s\)-steps. Likewise every \(s\)-step adds \(1\) to \(y\), and that contribution may later be doubled by later \(r\)-steps.
If the \(i\)-th \(r\)-step has \(\sigma_i\) later letters \(s\) after it, and the \(j\)-th \(s\)-step has \(\rho_j\) later letters \(r\) after it, then the final coordinates are
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
This formula explains why the search is delicate: the same multiset of letters can produce very different results depending on their order.
From the representation above, each \(r\)-contribution lies between \(1\) and \(2^S\), so
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
Similarly, each \(s\)-contribution lies between \(1\) and \(2^R\), so
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
During the recursion the implementation applies the same idea to a partial state \((x,y)\) with remaining counts \(r_{\mathrm{rem}}\) and \(s_{\mathrm{rem}}\). It computes
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
Therefore every possible completion satisfies
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$$
If \(0\notin[\Delta_{\min},\Delta_{\max}]\), no completion can possibly end with equality, so that entire branch is discarded immediately. This is a necessary condition, not a full characterization, but it cuts away most of the hopeless search space.
For fixed targets \(R\) and \(S\), define
$$C(x,y,a,b)=\text{number of valid completions from state }(x,y)\text{ after already using }a\text{ letters }r\text{ and }b\text{ letters }s.$$
The recursive structure is immediate:
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
with the understanding that a branch is used only if its corresponding operation count has not yet reached the target.
The terminal rule is
$$C(x,y,R,S)=\mathbf{1}_{x=y},$$
and any state with \(x=y\) before all letters are consumed is rejected, because equality must occur only at the final step.
The implementation does not store the exact count. It stores only \(0\), \(1\), or \(2\), where \(2\) means “at least two”. That is enough because the outer search only needs to distinguish impossible, unique, and non-unique cases.
For each total length \(m\), every split
$$R+S=m,\qquad 0\le R\le m$$
is tested. For that fixed pair, the memoized recursion determines whether there are no valid words, exactly one valid word, or several. If at least one valid word exists, the implementation can reconstruct a witness by repeatedly moving to a child state whose memoized count is positive.
The unrestricted scan over all \(m\) finds the first successful case at
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
The final output phase then scans only even \(m\) and returns the first even length for which the valid word is unique across all tested splits. That first even solution occurs at \(m=96\), with returned value
$$25332747903959376.$$
Consider the unrestricted success found at \(m=9\) with \(R=4\) and \(S=5\). The interval test at the initial state gives
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
Because the two intervals overlap, equality is not ruled out. One valid word is
"rssssrsrr", which evolves as
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
This is exactly the shortest successful equality checked by the implementation before the even-length output search begins.
The C++, Python, and Java implementations all follow the same structure. For each target pair \((R,S)\), they memoize states determined by the current coordinates together with how many times each operation has already been used. Before recursing, they apply the interval test above; if equality is outside the reachable final-difference range, that state returns immediately.
Whenever a state is not pruned, the implementation explores the two possible next moves, truncates the total count at \(2\), and stores that result in the memo table. If a positive count is found for a candidate \((R,S)\), one witness word is reconstructed by following a child whose memoized count remains positive. That witness is then simulated explicitly to confirm that equality occurs at the end and nowhere earlier.
The C++ implementation also performs two built-in checkpoints: first it confirms the shortest unrestricted equality at \(m=9\) with final value \(1476\), then it confirms that the first even-length answer is unique. The final printed value is
$$25332747903959376.$$
For a fixed pair \((R,S)\), naive enumeration would inspect all \(\binom{R+S}{R}\) words, which is exponential in the total length. Memoization collapses repeated subproblems with the same current state, and the interval bound removes large parts of the recursion tree before they branch further.
Even with those improvements, there is no simple polynomial worst-case bound coming from the code alone, because the numerical states grow under repeated doubling and the number of distinct reachable states still depends on the search path. The practical cost is therefore best described as exponential search with strong pruning. Memory usage is proportional to the number of memoized states for the current \((R,S)\), plus the cost of storing integers large enough to survive many doublings.
Wir starten bei \((45,90)\) und dürfen die beiden Operationen
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1)$$
anwenden. Gesucht sind Wörter aus \(r\) und \(s\), die erst am Ende die Gleichheit \(x=y\) erreichen, nicht schon in einem früheren Zwischenzustand. Die Implementierung fixiert zunächst Anzahlen \(R\) und \(S\) der beiden Operationen, zählt für dieses Paar die gültigen Wörter, kürzt die Anzahl auf \(0\), \(1\) oder \(\ge 2\) und durchsucht dann die Gesamtlängen \(m=R+S\). Ein vorbereitender unbeschränkter Scan findet bereits eine 9-Schritt-Gleichheit mit Wert \(1476\); die eigentliche Ausgabe-Suche betrachtet danach nur gerade Längen und liefert den ersten Fall mit eindeutigem gültigem Wort.
Die Schwierigkeit liegt darin, dass die Reihenfolge entscheidend ist: Die beiden Operationen kommutieren nicht, und jedes spätere Verdoppeln verstärkt frühere additive Beiträge. Deshalb kombiniert das Programm eine exakte Rekursion mit einer starken mathematischen Abschätzung zum Abschneiden aussichtsloser Zweige.
Seien wir gerade in \((x,y)\) und wollen noch genau \(R\) Buchstaben \(r\) und \(S\) Buchstaben \(s\) verwenden. Jeder \(r\)-Schritt addiert \(1\) zu \(x\), aber diese \(1\) kann durch spätere \(s\)-Schritte noch mehrfach verdoppelt werden. Analog addiert jeder \(s\)-Schritt \(1\) zu \(y\), und spätere \(r\)-Schritte können diesen Beitrag verdoppeln.
Hat der \(i\)-te \(r\)-Schritt noch \(\sigma_i\) spätere \(s\)-Schritte hinter sich und der \(j\)-te \(s\)-Schritt noch \(\rho_j\) spätere \(r\)-Schritte hinter sich, dann gilt
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
Damit sieht man sofort, warum die Suche nicht nur von den Anzahlen \(R\) und \(S\), sondern auch von der genauen Wortreihenfolge abhängt.
Jeder Beitrag eines \(r\)-Schritts liegt zwischen \(1\) und \(2^S\). Also gilt
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
Ebenso liegt jeder Beitrag eines \(s\)-Schritts zwischen \(1\) und \(2^R\), also
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
Im rekursiven Teil betrachtet die Implementierung einen Zwischenzustand \((x,y)\) mit Restanzahlen \(r_{\mathrm{rem}}\) und \(s_{\mathrm{rem}}\). Daraus folgen die sicheren Grenzen
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
Somit ist jede mögliche Enddifferenz in
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}$$
enthalten. Liegt \(0\) nicht in diesem Intervall, kann keine Fortsetzung zur Gleichheit führen, und der gesamte Ast wird sofort verworfen. Das ist eine notwendige, nicht hinreichende Bedingung, aber praktisch sehr wirkungsvoll.
Für feste Zielwerte \(R\) und \(S\) definieren wir
$$C(x,y,a,b)=\text{Anzahl gültiger Fortsetzungen aus }(x,y)\text{ nach bereits }a\text{ mal }r\text{ und }b\text{ mal }s.$$
Die Rekursion lautet
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
wobei jeder Summand natürlich nur vorkommt, wenn die entsprechende Restanzahl noch positiv ist.
Am Ende gilt
$$C(x,y,R,S)=\mathbf{1}_{x=y},$$
und jeder Zustand mit vorzeitiger Gleichheit \(x=y\) wird ausgeschlossen, weil Gleichheit nur im letzten Schritt erlaubt ist.
Gespeichert wird nicht die exakte Anzahl, sondern nur \(0\), \(1\) oder \(2\), wobei \(2\) für „mindestens zwei“ steht. Mehr Information braucht die äußere Suche nicht.
Für jede Gesamtlänge \(m\) werden alle Zerlegungen
$$R+S=m,\qquad 0\le R\le m$$
durchprobiert. Für jedes Paar entscheidet die memoisierten Rekursion, ob es keine, genau eine oder mehrere gültige Fortsetzungen gibt. Sobald ein positives Ergebnis vorliegt, kann ein konkretes Wort rekonstruiert werden, indem man wiederholt in einen Nachfolgezustand mit positiver gespeicherter Anzahl geht.
Der unbeschränkte Scan über alle \(m\) findet den ersten Erfolg bei
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
Die eigentliche Ausgabephase durchsucht danach nur gerade \(m\) und gibt die erste gerade Länge mit eindeutigem gültigem Wort zurück. Dieser erste gerade Treffer liegt bei \(m=96\) und liefert
$$25332747903959376.$$
Betrachten wir den unbeschränkten Erfolg bei \(m=9\) mit \(R=4\) und \(S=5\). Der Intervalltest am Startzustand ergibt
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
Die Intervalle überlappen also, Gleichheit ist nicht ausgeschlossen. Ein gültiges Wort ist
"rssssrsrr", mit Verlauf
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
Genau dieser 9-Schritt-Erfolg dient in der Implementierung als Kontrollpunkt vor der eigentlichen Suche nach der geraden Lösung.
Die C++-, Python- und Java-Implementierungen haben dieselbe Struktur. Für jedes Zielpaar \((R,S)\) memoisiert der Algorithmus Zustände, die durch die aktuellen Koordinaten und die bereits verwendeten Anzahlen beider Operationen bestimmt sind. Vor jedem rekursiven Abstieg wird der Intervalltest angewendet; liegt \(0\) außerhalb des erreichbaren Differenzbereichs, endet der Zustand sofort.
Wird ein Zustand nicht abgeschnitten, untersucht die Implementierung die beiden möglichen Folgeschritte, kürzt die Gesamtzahl auf höchstens \(2\) und speichert dieses Ergebnis. Bei positiver Anzahl rekonstruiert sie anschließend ein konkretes Wort, indem sie stets einen Nachfolger mit positiver gespeicherter Anzahl wählt. Dieses Wort wird dann noch einmal explizit simuliert, um zu prüfen, dass Gleichheit wirklich erst am Ende auftritt.
Zusätzlich enthält die C++-Fassung zwei eingebaute Prüfwerte: zuerst den kürzesten unbeschränkten Treffer mit \(m=9\) und Wert \(1476\), danach die Eindeutigkeit der ersten geraden Lösung. Der ausgegebene Wert ist
$$25332747903959376.$$
Für ein festes Paar \((R,S)\) müsste eine naive Enumeration alle \(\binom{R+S}{R}\) Wörter untersuchen und wäre damit exponentiell in der Gesamtlänge. Memoisierung fasst gleiche Teilprobleme zusammen, und die Intervallschranke entfernt viele Äste schon vor weiterem Verzweigen.
Trotzdem ergibt sich aus dem Code keine einfache polynomielle Worst-Case-Schranke, weil die Zahlen unter wiederholten Verdoppelungen wachsen und die Zahl der wirklich verschiedenen Zustände weiterhin vom Suchverlauf abhängt. Praktisch handelt es sich also um exponentielle Suche mit starker Beschneidung. Der Speicherverbrauch ist proportional zur Anzahl memoisierten Zustände für das aktuelle \((R,S)\), zuzüglich der Kosten für ganzzahlige Typen, die viele Verdoppelungen sicher aufnehmen können.
Başlangıç noktası \((45,90)\) ve izin verilen iki işlem
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1)$$
şeklindedir. Geçerli bir kelime, yalnızca son adımda \(x=y\) eşitliğine ulaşan; daha önceki ara durumlarda eşitliği hiç görmeyen \(r\) ve \(s\) dizisidir. Uygulama önce \(R\) adet \(r\) ve \(S\) adet \(s\) içeren sabit bir bileşimi ele alır, bu çift için kaç geçerli kelime olduğunu sayar, sonucu \(0\), \(1\) veya \(\ge 2\) olarak kırpar ve daha sonra toplam uzunluk \(m=R+S\) üzerinde arama yapar. Hazırlık amaçlı serbest tarama, 9 adımda \(1476\) değerine ulaşan bir eşitlik bulur; asıl çıktı araması ise yalnızca çift uzunlukları tarayıp ilk tekil çözümü döndürür.
Zorluk, işlem sırasının kritik olmasından gelir: iki işlem değişmeli değildir ve daha sonra gelen her ikiyle çarpma, daha önce yapılmış toplamsal katkıları büyütür. Bu yüzden program, tam doğruluk veren özyinelemeyi güçlü bir matematiksel budama kuralıyla birleştirir.
Şu anda \((x,y)\) durumunda olduğumuzu ve bundan sonra tam olarak \(R\) adet \(r\) ile \(S\) adet \(s\) kullanacağımızı düşünelim. Her \(r\) adımı \(x\)'e \(1\) ekler; fakat bu \(1\), daha sonra gelen bazı \(s\) adımları tarafından ikiyle çarpılabilir. Benzer biçimde her \(s\) adımı \(y\)'ye \(1\) ekler ve sonraki \(r\) adımları bu katkıyı büyütebilir.
Eğer \(i\). \(r\) adımından sonra \(\sigma_i\) tane \(s\) kalıyorsa ve \(j\). \(s\) adımından sonra \(\rho_j\) tane \(r\) kalıyorsa, son durum
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}$$
olur. Aynı \(R\) ve \(S\) değerleri için bile farklı sıra seçimlerinin niçin farklı sonuçlar doğurduğu bu formülden açıkça görülür.
Her \(r\) katkısı en az \(1\), en fazla \(2^S\) olabilir. Dolayısıyla
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
Aynı şekilde her \(s\) katkısı en az \(1\), en fazla \(2^R\) olduğundan
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
Özyineleme sırasında uygulama, kalan adım sayıları \(r_{\mathrm{rem}}\) ve \(s_{\mathrm{rem}}\) olan ara bir \((x,y)\) durumuna şu sınırları uygular:
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
Böylece her olası tamamlanış için
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}$$
elde edilir. Eğer \(0\) bu aralığın dışında kalıyorsa, hiçbir devam yolu eşitliğe ulaşamaz ve ilgili dal anında budanır. Bu koşul yeterli değil ama güçlü bir zorunlu koşuldur.
Sabit \(R\) ve \(S\) için
$$C(x,y,a,b)=\text{şu ana kadar }a\text{ kez }r\text{ ve }b\text{ kez }s\text{ kullanıldıktan sonra }(x,y)\text{ durumundan kalan geçerli tamamlama sayısı}$$
olarak tanımlansın. Özyineleme doğrudan
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1)$$
şeklindedir; tabii ilgili işlem hedef sayısına henüz ulaşmadıysa o dal kullanılır.
Sınır durumu
$$C(x,y,R,S)=\mathbf{1}_{x=y}$$
şeklindedir. Ayrıca bütün harfler tüketilmeden önce \(x=y\) olursa bu durum geçersiz sayılır; çünkü eşitlik yalnızca son adımda görünmelidir.
Uygulama tam sayıyı saklamaz; sadece \(0\), \(1\) veya \(2\) değerini saklar ve \(2\) burada “en az iki tane” anlamına gelir. Dış arama için ihtiyaç duyulan tek bilgi budur.
Her \(m\) için
$$R+S=m,\qquad 0\le R\le m$$
şeklindeki tüm ayrımlar denenir. Her çift için memoize edilmiş özyineleme, hiç çözüm olmadığını, tek çözüm bulunduğunu veya birden fazla çözüm bulunduğunu belirler. Eğer olumlu bir sayı elde edilirse, kayıtlı sayısı pozitif olan bir alt duruma gidilerek örnek bir kelime geri kurulabilir.
Tüm uzunluklar üzerindeki serbest tarama ilk başarıyı
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476$$
noktasında bulur. Asıl çıktı aşaması ise yalnızca çift \(m\) değerlerini tarar ve bütün ayrımlar arasında tek geçerli kelime üreten ilk çift uzunluğu döndürür. Bu ilk çift çözüm \(m=96\) için gelir ve çıktı değeri
$$25332747903959376$$
olur.
Serbest taramanın bulduğu \(m=9\), \(R=4\), \(S=5\) örneğini ele alalım. Başlangıç durumundaki aralık testi
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520$$
sonucunu verir. Aralıklar çakıştığı için eşitlik imkansız değildir. Geçerli bir kelime
"rssssrsrr"
olup şu yolu izler:
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
Bu da uygulamanın çift uzunluk aramasına başlamadan önce doğruladığı en kısa serbest eşitliktir.
C++, Python ve Java uygulamaları aynı mantığı izler. Her \((R,S)\) çifti için, mevcut koordinatları ve şimdiye kadar kullanılan işlem sayılarını birlikte anahtar yapan bir memo tablosu kurulur. Her özyinelemeli çağrıdan önce yukarıdaki fark aralığı testi uygulanır; \(0\) erişilebilir aralığın dışında kalıyorsa o durum hemen sonlandırılır.
Bir durum budanmazsa, iki olası sonraki adım incelenir, toplam sayı en fazla \(2\) olacak şekilde kırpılır ve sonuç tabloya yazılır. Pozitif sayılı bir aday bulunduğunda, uygulama pozitif sayılı bir alt durumu izleyerek örnek kelimeyi yeniden kurar. Ardından bu kelime baştan simüle edilerek eşitliğin gerçekten yalnızca son adımda oluştuğu doğrulanır.
C++ sürümü ayrıca iki gömülü kontrol uygular: önce \(m=9\) ve \(1476\) için en kısa serbest eşitliği, sonra da ilk çift uzunluk çözümünün tekilliğini doğrular. Son yazdırılan değer
$$25332747903959376$$
olur.
Sabit bir \((R,S)\) çifti için saf kuvvet denemesi \(\binom{R+S}{R}\) adet kelimeyi incelemek zorunda kalır; bu da toplam uzunlukta üstel büyüme demektir. Memoization aynı alt problemleri birleştirir, aralık budaması ise dalların büyük kısmını daha derine inmeden keser.
Buna rağmen, yalnızca koda bakarak basit bir polinomik en kötü durum sınırı çıkarmak mümkün değildir; çünkü sayılar art arda ikiyle çarpıldıkça büyür ve gerçekten farklı durumların sayısı arama yoluna bağlı kalır. Bu yüzden pratik tanım, güçlü budamaya sahip üstel aramadır. Bellek tüketimi, o anki \((R,S)\) için saklanan durum sayısıyla ve çok sayıda ikiyle çarpma işlemini güvenle taşıyan tamsayıların maliyetiyle orantılıdır.
Se parte de \((45,90)\) y se permiten las dos operaciones
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$$
Una palabra válida es una secuencia finita de \(r\) y \(s\) que alcanza \(x=y\) exactamente al final, sin pasar antes por un estado intermedio con igualdad. La implementación fija primero un número \(R\) de letras \(r\) y un número \(S\) de letras \(s\), cuenta cuántas palabras válidas existen para ese par, reduce el resultado a \(0\), \(1\) o \(\ge 2\), y luego recorre las longitudes totales \(m=R+S\). Un barrido preliminar sin restricción encuentra una igualdad de 9 pasos con valor \(1476\); después, la búsqueda que produce la respuesta final se limita a longitudes pares y devuelve el primer caso par con una única palabra válida.
La dificultad central es que el orden importa: las operaciones no conmutan, y cada duplicación posterior amplifica contribuciones aditivas hechas antes. Por eso el programa combina una recursión exacta con una regla matemática de poda muy fuerte.
Supongamos que estamos en \((x,y)\) y que todavía queremos usar exactamente \(R\) letras \(r\) y \(S\) letras \(s\). Cada paso \(r\) añade \(1\) a \(x\), pero ese \(1\) puede ser duplicado por algunos pasos \(s\) posteriores. De forma análoga, cada paso \(s\) añade \(1\) a \(y\), y los pasos \(r\) que aparezcan después pueden volver a duplicar esa contribución.
Si el \(i\)-ésimo paso \(r\) deja \(\sigma_i\) letras \(s\) detrás de él, y el \(j\)-ésimo paso \(s\) deja \(\rho_j\) letras \(r\) detrás de él, entonces las coordenadas finales son
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
Esto muestra por qué no basta conocer cuántas veces aparece cada letra: la posición relativa de cada una cambia el resultado.
Cada contribución procedente de un paso \(r\) está entre \(1\) y \(2^S\), así que
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
De la misma forma, cada contribución de un paso \(s\) está entre \(1\) y \(2^R\), luego
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
Durante la recursión, la implementación trabaja con un estado parcial \((x,y)\) y con cantidades restantes \(r_{\mathrm{rem}}\) y \(s_{\mathrm{rem}}\). Entonces calcula
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
Por tanto, toda continuación posible satisface
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$$
Si \(0\notin[\Delta_{\min},\Delta_{\max}]\), la igualdad final es imposible y la rama se descarta en ese mismo punto. Es una condición necesaria, no suficiente, pero extremadamente útil como filtro.
Para valores fijos de \(R\) y \(S\), definimos
$$C(x,y,a,b)=\text{número de completaciones válidas desde }(x,y)\text{ tras haber usado }a\text{ letras }r\text{ y }b\text{ letras }s.$$
La recurrencia es
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
entendiendo que cada sumando solo aparece si todavía queda disponible la operación correspondiente.
La condición terminal es
$$C(x,y,R,S)=\mathbf{1}_{x=y},$$
y todo estado con \(x=y\) antes de consumir todas las letras se rechaza, porque la igualdad solo es válida en el último paso.
La implementación no guarda el recuento exacto: solo guarda \(0\), \(1\) o \(2\), donde \(2\) significa “dos o más”. Eso basta para distinguir entre ausencia, unicidad y multiplicidad.
Para cada longitud \(m\), se prueban todas las descomposiciones
$$R+S=m,\qquad 0\le R\le m.$$
Para cada par, la recursión memoizada decide si no existe ninguna palabra válida, si existe exactamente una o si existen varias. Cuando el recuento es positivo, la implementación puede reconstruir un testigo avanzando siempre hacia un estado hijo con recuento positivo.
El barrido sin restricción sobre todos los \(m\) encuentra el primer éxito en
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
Después, la fase que genera la respuesta final examina solo \(m\) pares y devuelve la primera longitud par cuya palabra válida es única entre todas las particiones ensayadas. Ese primer caso par aparece en \(m=96\) y produce
$$25332747903959376.$$
Tomemos el éxito sin restricción con \(m=9\), \(R=4\) y \(S=5\). El test de intervalos en el estado inicial da
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
Como los intervalos se superponen, la igualdad no queda descartada. Una palabra válida es
"rssssrsrr", cuya evolución es
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
Ese es exactamente el primer caso exitoso que la implementación usa como comprobación antes de iniciar la búsqueda final sobre longitudes pares.
Las implementaciones en C++, Python y Java siguen la misma arquitectura. Para cada par objetivo \((R,S)\), memorizan estados definidos por las coordenadas actuales y por cuántas veces se ha usado ya cada operación. Antes de profundizar en la recursión, aplican la prueba del intervalo de diferencia; si \(0\) queda fuera del rango alcanzable, ese estado termina de inmediato.
Si el estado sobrevive a la poda, la implementación explora los dos siguientes movimientos posibles, trunca el total en \(2\) y almacena el resultado. Cuando aparece un recuento positivo, reconstruye una palabra testigo siguiendo un hijo cuyo recuento memoizado siga siendo positivo. Después simula explícitamente esa palabra para confirmar que la igualdad aparece al final y en ningún paso intermedio.
La versión en C++ además contiene dos verificaciones integradas: primero confirma el éxito sin restricción de longitud \(9\) y valor \(1476\), y luego confirma que la primera solución de longitud par es única. El valor final impreso es
$$25332747903959376.$$
Para un par fijo \((R,S)\), una enumeración ingenua tendría que recorrer todas las \(\binom{R+S}{R}\) palabras, así que el crecimiento es exponencial en la longitud total. La memoización fusiona subproblemas repetidos y la poda por intervalos elimina muchos subárboles antes de que se desarrollen.
Aun así, a partir del código no se obtiene una cota polinómica simple en el peor caso, porque los estados numéricos crecen con las duplicaciones y la cantidad de estados distintos todavía depende del recorrido concreto. La descripción más fiel es, por tanto, búsqueda exponencial con poda fuerte. La memoria es proporcional al número de estados memoizados para el \((R,S)\) actual, además del coste de almacenar enteros capaces de soportar muchas duplicaciones.
起点是 \((45,90)\)，允许执行两种操作
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$$
所谓有效路径，是指由 \(r\) 与 \(s\) 组成的有限字符串，它在最后一步恰好满足 \(x=y\)，并且在此前任何中间状态都没有出现过 \(x=y\)。实现方式是：先固定 \(r\) 的使用次数 \(R\) 和 \(s\) 的使用次数 \(S\)，统计该组合下有效字符串的数量，再把这个数量截断成 \(0\)、\(1\) 或 \(\ge 2\)，随后按照总长度 \(m=R+S\) 逐步搜索。作为校验，程序先做一次不受奇偶限制的搜索，找到一个 9 步达到 \(1476\) 的相等案例；真正输出答案的阶段则只扫描偶数长度，并返回第一个拥有唯一有效路径的偶数长度结果。
难点在于顺序会改变结果：这两个操作不交换，而且后面的翻倍会放大前面加出来的贡献。因此程序并不是直接枚举全部字符串，而是把精确递归与一个很强的数学剪枝条件结合起来。
设当前状态是 \((x,y)\)，接下来还要使用恰好 \(R\) 个 \(r\) 和 \(S\) 个 \(s\)。每执行一次 \(r\)，会先给 \(x\) 加上 \(1\)；但这个 \(1\) 之后可能会被若干个 \(s\) 操作继续乘以 \(2\)。同理，每执行一次 \(s\)，会先给 \(y\) 加上 \(1\)，之后也可能被若干个 \(r\) 操作继续翻倍。
如果第 \(i\) 个 \(r\) 之后还剩 \(\sigma_i\) 个 \(s\)，第 \(j\) 个 \(s\) 之后还剩 \(\rho_j\) 个 \(r\)，那么最终坐标满足
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
这个表达式清楚说明了：即使 \(R\) 和 \(S\) 相同，不同的字母排列顺序也会导致完全不同的终点。
对于每一个 \(r\) 带来的贡献，最小只能是 \(1\)，最大可以是 \(2^S\)，因此有
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
类似地，每一个 \(s\) 对 \(y\) 的贡献至少是 \(1\)，至多是 \(2^R\)，所以
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
在递归过程中，程序面对的是某个中间状态 \((x,y)\)，以及还没使用的操作数 \(r_{\mathrm{rem}}\) 与 \(s_{\mathrm{rem}}\)。这时它计算
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
于是任何后续完成方式都必须满足
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$$
如果 \(0\) 根本不在区间 \([\Delta_{\min},\Delta_{\max}]\) 内，那么无论后续如何排列，最终都不可能满足 \(x=y\)，这一整棵递归分支就可以立刻剪掉。这个条件只是必要条件，不是充分条件，但已经足够强大。
在固定 \(R\) 与 \(S\) 的前提下，用 \(C(x,y,a,b)\) 表示：从状态 \((x,y)\) 出发，在已经用了 \(a\) 个 \(r\) 和 \(b\) 个 \(s\) 之后，剩余的有效完成方式数量。
$$C(x,y,a,b)$$
递推关系直接来自下一步只能二选一：
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
当然，只有对应操作还没有用满时，那一项才真正存在。
终止条件是
$$C(x,y,R,S)=\mathbf{1}_{x=y},$$
而且如果在尚未用完全部字母之前就已经出现 \(x=y\)，该状态会被直接判为无效，因为题目要求相等只能发生在最后一步。
实现时并不保存精确计数，而只保存 \(0\)、\(1\) 或 \(2\)。这里的 \(2\) 表示“至少两条”。这是因为外层搜索只关心三件事：没有解、唯一解、多于一个解。
对于每个总长度 \(m\)，程序都会尝试所有拆分
$$R+S=m,\qquad 0\le R\le m.$$
对每一组 \((R,S)\)，记忆化递归会判断有效路径数是 \(0\)、\(1\) 还是至少 \(2\)。如果某个组合存在正数条有效路径，程序就可以顺着“子状态计数仍为正”的方向一步步往下走，从而重建出一条具体的见证路径。
不限制长度奇偶时，第一次成功出现在
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
真正负责输出答案的阶段则只考察偶数 \(m\)，并返回第一个在所有拆分中都表现为“唯一有效路径”的偶数长度。这个最早的偶数解出现在 \(m=96\)，对应的公共终值是
$$25332747903959376.$$
来看程序先找到的 9 步成功案例，其中 \(R=4\)、\(S=5\)。在初始状态做区间判断时，有
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
这两个区间有交集，因此“最终相等”并没有被剪枝规则排除。程序重建出的一个有效字符串是
"rssssrsrr"，其状态演化为
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476) \end{aligned}$$
这正是程序在进入偶数长度搜索前用来校验整体逻辑的最短成功路径。
C++、Python 和 Java 实现采用完全一致的思路。对于每个候选 \((R,S)\)，它们都用“当前坐标 + 两种操作已使用次数”作为状态键进行记忆化。每次递归展开前，先应用上面的差值区间测试；如果 \(0\) 不在可达区间内，就立刻返回，不再继续搜索。
若一个状态没有被剪掉，程序就尝试两个可能的后继操作，把总计数截断到 \(2\) 以内，并把结果写入记忆表。一旦某个 \((R,S)\) 出现正数条有效路径，就沿着“记忆值仍为正”的子状态重建出一条见证路径，随后再显式模拟一次，确认相等只发生在最后一步而不会提前发生。
C++ 实现另外还带有两个内部校验点：先验证不限制奇偶时的最短成功长度 \(m=9\) 及其终值 \(1476\)，再验证第一个偶数长度答案的唯一性。最终打印的数值是
$$25332747903959376.$$
如果固定 \((R,S)\) 后直接暴力枚举，那么需要检查全部 \(\binom{R+S}{R}\) 个字符串，因此时间增长本质上是指数级。记忆化会把重复子问题合并，而区间剪枝会在递归树尚未扩张之前就砍掉大量明显不可能成功的分支。
即便如此，仅从代码结构本身仍然无法推出一个简单的多项式最坏情况上界，因为状态中的数值会随着不断翻倍而增长，可达的不同状态数仍取决于搜索实际经过的路径。所以更准确的描述是：这是一个带有强剪枝的指数搜索。空间开销与当前 \((R,S)\) 下被记忆化的状态数量成正比，同时还要承担大整数存储的成本。
Стартовая точка равна \((45,90)\), а разрешены две операции
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$$
Допустимым считается такое слово из букв \(r\) и \(s\), которое приводит к равенству \(x=y\) только в самом конце и ни на одном более раннем промежуточном шаге. Реализация сначала фиксирует числа \(R\) и \(S\), то есть сколько раз должны встретиться операции каждого типа, затем считает число допустимых слов для этой пары, сокращая результат до \(0\), \(1\) или \(\ge 2\), и после этого перебирает общую длину \(m=R+S\). Предварительная проверка без ограничения по чётности находит 9-шаговое равенство со значением \(1476\); основной поиск ответа затем рассматривает только чётные длины и возвращает первый чётный случай с единственным допустимым словом.
Главная трудность состоит в том, что порядок букв важен: операции не коммутируют, а каждое последующее удвоение усиливает более ранние добавки. Поэтому программа использует точную рекурсию, усиленную мощным правилом отсечения.
Пусть текущая точка равна \((x,y)\), и далее нужно выполнить ровно \(R\) операций \(r\) и \(S\) операций \(s\). Каждый шаг \(r\) прибавляет \(1\) к \(x\), но затем эта единица может быть ещё несколько раз удвоена последующими буквами \(s\). Аналогично каждый шаг \(s\) прибавляет \(1\) к \(y\), и последующие буквы \(r\) могут удвоить этот вклад.
Если после \(i\)-й буквы \(r\) остаётся \(\sigma_i\) будущих букв \(s\), а после \(j\)-й буквы \(s\) остаётся \(\rho_j\) будущих букв \(r\), то конечные координаты выражаются так:
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
Именно здесь видно, почему одинаковые количества букв ещё не определяют итог: всё зависит от взаимного расположения этих букв.
Каждый вклад от буквы \(r\) лежит между \(1\) и \(2^S\), поэтому
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
Точно так же каждый вклад от буквы \(s\) лежит между \(1\) и \(2^R\), следовательно
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
Во время рекурсии рассматривается промежуточное состояние \((x,y)\) с оставшимися числами ходов \(r_{\mathrm{rem}}\) и \(s_{\mathrm{rem}}\). Тогда вычисляются величины
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
Значит, для любого завершения выполняется
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$$
Если \(0\notin[\Delta_{\min},\Delta_{\max}]\), конечное равенство невозможно, и вся ветвь отбрасывается сразу. Это только необходимое условие, но на практике оно даёт очень сильное сокращение дерева поиска.
Для фиксированных \(R\) и \(S\) определим
$$C(x,y,a,b)=\text{число допустимых продолжений из }(x,y)\text{ после уже использованных }a\text{ букв }r\text{ и }b\text{ букв }s.$$
Рекуррентное соотношение имеет вид
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
причём соответствующий член присутствует только тогда, когда нужная операция ещё не израсходована полностью.
Граничное условие:
$$C(x,y,R,S)=\mathbf{1}_{x=y}.$$
Любое состояние с \(x=y\) до исчерпания всех букв объявляется недопустимым, потому что равенство разрешено только на последнем шаге.
Точная мощность множества путей не сохраняется: сохраняются только значения \(0\), \(1\) и \(2\), где \(2\) означает «не меньше двух». Для внешнего поиска этого вполне достаточно.
Для каждой длины \(m\) проверяются все разбиения
$$R+S=m,\qquad 0\le R\le m.$$
Для каждой пары memoized-рекурсия определяет, нет ли допустимых слов вовсе, существует ли ровно одно или существует несколько. Если число положительно, программа может восстановить конкретное слово, каждый раз переходя в дочернее состояние с положительным сохранённым значением.
Неограниченный по чётности просмотр всех \(m\) находит первый успех при
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
Затем фаза, которая формирует окончательный ответ, рассматривает только чётные \(m\) и возвращает первую чётную длину, для которой допустимое слово единственно среди всех проверенных разбиений. Этот первый чётный случай возникает при \(m=96\) и даёт значение
$$25332747903959376.$$
Возьмём найденный программой 9-шаговый успех с \(R=4\) и \(S=5\). На стартовом состоянии интервальная проверка даёт
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
Интервалы пересекаются, значит равенство не исключено. Один допустимый путь имеет вид
"rssssrsrr" и развивается так:
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
Именно этот кратчайший успех программа использует как контрольную точку перед переходом к поиску по чётным длинам.
Реализации на C++, Python и Java устроены одинаково. Для каждой целевой пары \((R,S)\) они мемоизируют состояния, задаваемые текущими координатами и количеством уже использованных операций каждого типа. Перед любым рекурсивным углублением применяется проверка интервала для конечной разности; если ноль лежит вне достижимого диапазона, состояние завершается немедленно.
Если отсечения нет, реализация рассматривает два возможных следующих шага, ограничивает суммарный счёт сверху значением \(2\) и заносит этот результат в таблицу. Когда для некоторого кандидата \((R,S)\) найден положительный счёт, программа восстанавливает одно свидетельствующее слово, последовательно выбирая дочернее состояние с положительным memoized-значением. Затем это слово отдельно симулируется, чтобы убедиться: равенство действительно возникает только в самом конце.
В версии C++ также встроены две проверки: сначала подтверждается кратчайший неограниченный успех длины \(9\) со значением \(1476\), затем подтверждается уникальность первого ответа чётной длины. Напечатанное итоговое значение равно
$$25332747903959376.$$
Для фиксированной пары \((R,S)\) наивный перебор должен был бы просмотреть все \(\binom{R+S}{R}\) слова, то есть имел бы экспоненциальную зависимость от общей длины. Мемоизация склеивает повторяющиеся подзадачи, а интервальное отсечение устраняет многие ветви ещё до их разрастания.
Тем не менее из одного лишь кода нельзя вывести простую полиномиальную оценку худшего случая: значения координат растут из-за многократных удвоений, а число различных достижимых состояний всё ещё зависит от конкретного хода поиска. Поэтому наиболее честное описание таково: это экспоненциальный поиск с очень сильным отсечением. Память пропорциональна числу мемоизированных состояний для текущей пары \((R,S)\), а также стоимости хранения достаточно больших целых чисел.
نبدأ من النقطة \((45,90)\)، ومعنا العمليتان
$$r:(x,y)\mapsto(x+1,2y),\qquad s:(x,y)\mapsto(2x,y+1).$$
المسار المقبول هو سلسلة من الحرفين \(r\) و\(s\) تصل إلى الحالة \(x=y\) في النهاية فقط، من دون أن تظهر المساواة في أي خطوة وسطية قبل الخطوة الأخيرة. أسلوب التنفيذ هو أن يثبت أولاً عدد مرات استعمال \(r\) ويسميه \(R\)، وعدد مرات استعمال \(s\) ويسميه \(S\)، ثم يحسب عدد السلاسل المقبولة لذلك الزوج، ويختزل النتيجة إلى \(0\) أو \(1\) أو \(\ge 2\)، وبعد ذلك يبحث على أطوال كلية \(m=R+S\). يوجد فحص تمهيدي غير مقيّد بالزوجية يجد مساواة بطول 9 خطوات وقيمة نهائية \(1476\)، ثم تأتي مرحلة استخراج الجواب الفعلي فتفحص الأطوال الزوجية فقط وتعيد أول طول زوجي يملك مساراً صحيحاً وحيداً.
الصعوبة الأساسية أن ترتيب الخطوات يغيّر النتيجة: العمليتان غير تبادليتين، وكل عملية تضاعف لاحقة تكبّر الإضافات التي حدثت قبلها. لذلك لا يعتمد البرنامج على تعداد مباشر لكل الكلمات، بل يجمع بين عودية دقيقة وقاعدة تقليم رياضية قوية.
افترض أننا عند الحالة \((x,y)\)، وما يزال علينا استعمال \(R\) حروف من النوع \(r\) و\(S\) حروف من النوع \(s\). كل خطوة \(r\) تضيف \(1\) إلى \(x\)، لكن هذه الوحدة قد تُضرب لاحقاً في \(2\) عدة مرات بسبب خطوات \(s\) التي تأتي بعدها. وبالمثل فإن كل خطوة \(s\) تضيف \(1\) إلى \(y\)، ثم يمكن لخطوات \(r\) اللاحقة أن تضاعف هذا الأثر.
إذا كان بعد خطوة \(r\) رقم \(i\) عدد \(\sigma_i\) من خطوات \(s\) المتبقية، وبعد خطوة \(s\) رقم \(j\) عدد \(\rho_j\) من خطوات \(r\) المتبقية، فإن الإحداثيات النهائية تساوي
$$x_{\mathrm{final}}=x\,2^S+\sum_{i=1}^{R}2^{\sigma_i},\qquad y_{\mathrm{final}}=y\,2^R+\sum_{j=1}^{S}2^{\rho_j}.$$
وهذا يوضح مباشرة أن معرفة عدد الحروف وحده لا تكفي؛ فترتيبها داخل الكلمة يغيّر القيمة النهائية.
كل مساهمة قادمة من خطوة \(r\) تقع بين \(1\) و\(2^S\)، ولذلك نحصل على
$$x\,2^S+R\le x_{\mathrm{final}}\le x\,2^S+R\,2^S.$$
وبالصورة نفسها، كل مساهمة من خطوة \(s\) تقع بين \(1\) و\(2^R\)، ومن ثم
$$y\,2^R+S\le y_{\mathrm{final}}\le y\,2^R+S\,2^R.$$
أثناء العودية يتعامل التنفيذ مع حالة جزئية \((x,y)\) ومع عددين متبقيين \(r_{\mathrm{rem}}\) و\(s_{\mathrm{rem}}\). عندئذ يحسب
$$x_{\min}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}},\qquad x_{\max}=x\,2^{s_{\mathrm{rem}}}+r_{\mathrm{rem}}\,2^{s_{\mathrm{rem}}},$$
$$y_{\min}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}},\qquad y_{\max}=y\,2^{r_{\mathrm{rem}}}+s_{\mathrm{rem}}\,2^{r_{\mathrm{rem}}}.$$
وبالتالي فإن كل إكمال ممكن يجب أن يحقق
$$\Delta_{\min}=x_{\min}-y_{\max}\le x_{\mathrm{final}}-y_{\mathrm{final}}\le x_{\max}-y_{\min}=\Delta_{\max}.$$
إذا كان الصفر خارج المجال \([\Delta_{\min},\Delta_{\max}]\)، فالوصول إلى \(x=y\) مستحيل مهما كان ترتيب ما تبقى من الخطوات، وعندها يُحذف ذلك الفرع مباشرة. هذا شرط لازم لا كافٍ، لكنه شديد الفاعلية في التقليص.
لزوج ثابت \((R,S)\)، نرمز بالعبارة \(C(x,y,a,b)\) إلى عدد الإكمالات الصحيحة المنطلقة من الحالة \((x,y)\) بعد استعمال \(a\) من \(r\) و\(b\) من \(s\).
$$C(x,y,a,b)$$
وعلاقة العودية هي
$$C(x,y,a,b)=C(x+1,2y,a+1,b)+C(2x,y+1,a,b+1),$$
مع ملاحظة أن كل حد يظهر فقط إذا كانت العملية المقابلة ما تزال متاحة ضمن الحصة المطلوبة.
أما شرط النهاية فهو
$$C(x,y,R,S)=\mathbf{1}_{x=y},$$
وأي حالة يتحقق فيها \(x=y\) قبل استهلاك جميع الحروف تعتبر غير صالحة، لأن المساواة يجب أن تظهر في النهاية فقط.
التنفيذ لا يخزّن العدد الحقيقي للمسارات، بل يخزّن فقط \(0\) أو \(1\) أو \(2\)، حيث تعني \(2\) هنا "اثنان أو أكثر". وهذا يكفي للتمييز بين عدم وجود حل، ووجود حل وحيد، ووجود أكثر من حل.
لكل طول كلي \(m\)، يتم اختبار جميع الحالات
$$R+S=m,\qquad 0\le R\le m.$$
ولكل زوج \((R,S)\)، تحدد العودية المحفوظة ما إذا كان عدد الكلمات الصحيحة صفراً أو واحداً أو أكثر من واحد. وإذا ظهر عدد موجب، يستطيع التنفيذ إعادة بناء شاهد فعلي باختيار حالة ابنة يبقى فيها العدد المحفوظ موجباً.
المسح غير المقيّد على جميع \(m\) يجد أول نجاح عند
$$m=9,\qquad (R,S)=(4,5),\qquad x_{\mathrm{final}}=y_{\mathrm{final}}=1476.$$
ثم تأتي مرحلة الجواب النهائي، فتفحص فقط القيم الزوجية لـ \(m\)، وتعيد أول طول زوجي تكون فيه الكلمة الصحيحة وحيدة عبر جميع التفكيكات المجربة. هذا أول ما يحدث عند \(m=96\)، والقيمة المرجعة هي
$$25332747903959376.$$
لنأخذ المثال الناجح غير المقيّد الذي وجده البرنامج عند \(m=9\) مع \(R=4\) و\(S=5\). اختبار المجال في البداية يعطي
$$x_{\min}=45\cdot 2^5+4=1444,\qquad x_{\max}=45\cdot 2^5+4\cdot 2^5=1584,$$
$$y_{\min}=90\cdot 2^4+5=1445,\qquad y_{\max}=90\cdot 2^4+5\cdot 2^4=1520.$$
وبما أن المجالين يتقاطعان، فإن المساواة النهائية ليست مستبعدة. إحدى الكلمات الصحيحة هي
"rssssrsrr"، وتتطور على النحو الآتي:
$$\begin{aligned} (45,90)&\xrightarrow{r}(46,180)\xrightarrow{s}(92,181)\xrightarrow{s}(184,182)\xrightarrow{s}(368,183)\xrightarrow{s}(736,184),\\ &\xrightarrow{r}(737,368)\xrightarrow{s}(1474,369)\xrightarrow{r}(1475,738)\xrightarrow{r}(1476,1476). \end{aligned}$$
وهذا هو بالضبط أقصر نجاح يتحقق منه التنفيذ قبل أن يبدأ البحث النهائي على الأطوال الزوجية.
تتبع تطبيقات C++ وPython وJava البنية نفسها. فلكل زوج هدف \((R,S)\)، يجري حفظ الحالات التي يحددها كل من الإحداثيين الحاليين وعدد مرات استعمال كل عملية حتى اللحظة. وقبل أي توسع عودي، يُطبَّق اختبار مجال الفارق النهائي؛ فإذا كان الصفر خارج المجال الممكن، تتوقف تلك الحالة فوراً.
إذا لم تُقصَّ الحالة، يفحص التنفيذ الخطوتين التاليتين الممكنتين، ويقص العدد الكلي عند \(2\)، ثم يخزن النتيجة. وعندما يجد زوجاً يعطي عدداً موجباً، يعيد بناء كلمة شاهدة عبر الانتقال دائماً إلى ابن ما دام عدده المحفوظ موجباً. وبعد ذلك يحاكي تلك الكلمة صراحةً للتأكد من أن المساواة لا تظهر إلا في الخطوة الأخيرة.
تتضمن نسخة C++ أيضاً نقطتي تحقق داخليتين: الأولى تؤكد أقصر نجاح غير مقيّد بطول \(9\) وقيمة \(1476\)، والثانية تؤكد فرادة أول جواب ذي طول زوجي. والقيمة المطبوعة في النهاية هي
$$25332747903959376.$$
لزوج ثابت \((R,S)\)، فإن التعداد الساذج يحتاج إلى فحص جميع الكلمات وعددها \(\binom{R+S}{R}\)، ولذلك يكون الزمن أسيّاً في الطول الكلي. أما الحفظ فيدمج المسائل الجزئية المتكررة، ويزيل اختبار المجال عدداً كبيراً من الأفرع قبل أن تتشعب أكثر.
ومع ذلك، لا يعطي الكود وحده حدّاً كثير الحدود بسيطاً في أسوأ حالة، لأن القيم العددية تنمو بفعل التضاعف المتكرر، كما أن عدد الحالات المختلفة فعلاً ما يزال مرتبطاً بمسار البحث نفسه. لذلك فإن الوصف الأدق هو: بحث أسي مع تقليم قوي. واستهلاك الذاكرة يتناسب مع عدد الحالات المحفوظة للزوج الحالي \((R,S)\)، إضافة إلى كلفة تمثيل أعداد صحيحة كبيرة تتحمل الكثير من عمليات التضعيف.