For each pair \(1 \le c,d \le 160\), let \(s=c+d\). We place nonnegative integers on a cycle of length \(s\), start from a single pulse \(k\) at one position, and then repeatedly perform a cyclic in-place averaging update with a floor. The key quantity is \(K(c,d)\), the largest starting value that still eventually dies out to the all-zero state.
Once \(K(c,d)\) is known, the problem asks for
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
A brute-force search over all starting values is impossible because the thresholds become large. The implementations succeed by exploiting the monotone structure of the update rule, a reduction by \(\gcd(c,d)\), and a further collapse of the reduced problem to one-dimensional threshold tables.
The whole problem is governed by a discrete dynamical system on a cycle. The useful mathematics is not an abstract template; it is the exact recurrence, the exact invariant regions, and the exact threshold structure used by the search.
Index the cycle by \(0,1,\dots,s-1\), and let the state after some number of elementary updates be \(x=(x_0,\dots,x_{s-1})\). The initial state is
\[ x_{s-1}=k, \qquad x_i=0 \text{ for } i\ne s-1. \]
At each elementary step, only one coordinate changes. If the current head position is \(h\), then the update is
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
and then the head advances to \(h+1 \bmod s\). Because \(s=c+d\), the same rule can also be written as
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor. \]
This is the exact recurrence implemented in all three languages. The process is asynchronous: values written earlier in the sweep are immediately visible to later updates in the same sweep.
Two facts drive the search.
First, the local map \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) is monotone in both inputs. So if two initial pulses satisfy \(k_1 \le k_2\), and we run the same update schedule on both, then the componentwise order is preserved forever. Larger initial data can never produce a smaller trajectory than smaller initial data.
Second, the dynamics has two obvious forward-invariant regions:
\[ x\equiv 0 \implies \text{all future states are } 0, \]
and
\[ x_i \ge 1 \text{ for every } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1, \]
so a state with no zeros can never reach the all-zero state later. This is why the implementations can stop as soon as either every entry is zero or every entry is positive.
There is also a simple boundedness invariant:
\[ 0 \le x_i \le k \qquad \text{for every coordinate and every time.} \]
No update can create a negative value or exceed the initial pulse.
Define the extinction predicate
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{if the trajectory started from } k \text{ reaches } 0,\\ 0, & \text{otherwise.} \end{cases} \]
By monotonicity, \(\mathcal{E}_{c,d}(k)\) is non-increasing in \(k\). Therefore the set of extinguishing initial values is an initial interval
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
This is the mathematical reason binary search is valid: once some \(k\) fails to die out, every larger \(k\) also fails.
Let
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
Since the update for position \(h\) reads from \(h+c \bmod s\), every dependency preserves the residue class modulo \(g\). So the cycle of length \(s=c+d\) splits into \(g\) independent smaller cycles, each of length
\[ \frac{s}{g}=r_c+r_d. \]
Only one of those residue classes contains the initial pulse. The other \(g-1\) classes start at zero and stay zero forever. Therefore the extinction threshold depends only on the reduced pair:
\[ K(c,d)=K(r_c,r_d). \]
This reduction is exact, not heuristic. It explains why the final summation always begins by dividing \(c\) and \(d\) by their gcd.
After the gcd reduction, the implementations do not build a full two-dimensional table of reduced thresholds. Instead they use a stronger structural relation and reconstruct every reduced pair from one-dimensional families.
Write
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
The reduced threshold used by the solver is then
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1. \end{cases} \]
So the two-parameter family is collapsed to the line \(K(1,n)\), plus a small exceptional strip for \(K(m,1)\). In particular, once \(K_1(1),K_1(2),\dots,K_1(239)\) are known, almost every reduced pair needed by the problem is already determined.
Here \(s=3\), so the initial state is \((0,0,k)\). The update repeatedly averages a position with the previous one on the 3-cycle.
For \(k=3\), one possible compressed trace is
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
So \(k=3\) does become extinct.
For \(k=4\), the process behaves differently:
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
Once the state is \((1,1,1)\), every coordinate is positive, so extinction is impossible from then on. Hence \(K(2,1)=3\), and therefore
\[ G(2,1)=2\cdot 3+1=7. \]
This small example captures the general pattern: monotonicity turns the dynamical question into a threshold search.
The C++, Python, and Java implementations simulate the in-place recurrence exactly for a fixed triple \((c,d,k)\). They maintain the cyclic state, the current head, and a counter of how many entries are zero. That counter gives two exact stopping conditions: all zero means extinction has been reached, while no zero means the state has entered the forward-invariant positive region and cannot die out anymore.
Each exact threshold is found by doubling an upper bound until extinction fails, then binary-searching between the last extinguishing value and the first non-extinguishing one. For the special family \(K_1(n)=K(1,n)\), the implementations use an eight-way cubic predictor indexed by \(n \bmod 8\) to place the initial search window near the true answer. That predictor changes only the speed of the search, not its correctness.
The one-dimensional table \(K_1(1),\dots,K_1(239)\) is the main precomputation. The C++ and Java implementations parallelize it across threads; the Python implementation uses multiple processes when available and falls back to serial evaluation if needed. For the branch \(K(m,1)\), a few small values are computed directly, and the larger ones are reconstructed from the same collapsed family with direct spot checks for safety.
For every pair \((c,d)\), the implementation first reduces it to \((r_c,r_d)\) by dividing by \(\gcd(c,d)\). It then recovers the needed threshold from the precomputed one-dimensional tables, forms
\[ G(c,d)=2K(r_c,r_d)+1, \]
and accumulates the result over all \(160^2\) pairs. Because the final answer is far larger than a machine word, the total is stored with arbitrary-precision integer arithmetic.
Let \(\tau(c,d,k)\) be the number of elementary updates performed before the extinction test for \((c,d,k)\) reaches one of its two exact stopping conditions. Then one threshold query costs
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
because doubling plus binary search makes only logarithmically many extinction tests.
The dominant work is the precomputation of the table \(K_1(1),\dots,K_1(239)\). After that, the final double sum over all \(c,d\le 160\) is cheap: each pair needs one gcd, one table lookup, and a few arithmetic operations. Memory usage is small. A single simulation stores at most \(c+d\le 320\) integers, and the precomputed tables themselves have only a few hundred entries.
Für jedes Paar \(1 \le c,d \le 160\) setzt man \(s=c+d\). Auf einem Zyklus der Länge \(s\) liegen nichtnegative ganze Zahlen. Anfangszustand ist ein einzelner Impuls \(k\) an genau einer Position; danach wird wiederholt eine zyklische In-Place-Mittelung mit Abrundung ausgeführt. Die zentrale Größe ist \(K(c,d)\): der größte Startwert, der trotzdem noch im Nullzustand endet.
Sobald \(K(c,d)\) bekannt ist, lautet die gesuchte Größe
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
Ein naiver Suchlauf über alle möglichen Startwerte wäre viel zu teuer. Die Lösung nutzt stattdessen die Monotonie des Updates, eine exakte Reduktion über \(\gcd(c,d)\) und eine weitere Verdichtung der reduzierten Fälle auf eindimensionale Tabellen.
Das Problem ist ein diskretes dynamisches System auf einem Kreis. Entscheidend sind die konkrete Rekursion, die Invarianten des Prozesses und die daraus folgende Schwellenstruktur.
Nummeriere die Plätze des Zyklus mit \(0,1,\dots,s-1\), und schreibe den Zustand als \(x=(x_0,\dots,x_{s-1})\). Der Anfangszustand ist
\[ x_{s-1}=k, \qquad x_i=0 \text{ für } i\ne s-1. \]
In einem elementaren Schritt ändert sich genau eine Koordinate. Befindet sich der Kopf gerade an Position \(h\), dann gilt
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
und anschließend wandert der Kopf zu \(h+1 \bmod s\). Wegen \(s=c+d\) kann man dieselbe Regel auch als
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor \]
lesen. Genau diese asynchrone In-Place-Dynamik berechnen die Implementierungen.
Die lokale Abbildung \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) ist in beiden Argumenten monoton. Startet man also mit \(k_1 \le k_2\), dann bleibt die komponentenweise Ordnung während des gesamten Ablaufs erhalten. Ein größerer Impuls kann die Entwicklung eines kleineren nie unterschreiten.
Außerdem gibt es zwei vorwärtsinvariante Bereiche:
\[ x\equiv 0 \implies \text{alle späteren Zustände bleiben } 0, \]
und
\[ x_i \ge 1 \text{ für alle } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
Ein vollständig positiver Zustand kann also nie mehr zum Nullzustand zurückkehren. Deshalb dürfen die Programme genau dann abbrechen, wenn entweder alle Einträge null oder keiner mehr null ist.
Zugleich bleibt jede Koordinate stets zwischen 0 und dem Anfangsimpuls:
\[ 0 \le x_i \le k. \]
Definiere das Prädikat
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{wenn der Startwert } k \text{ den Nullzustand erreicht},\\ 0, & \text{sonst.} \end{cases} \]
Aus der Monotonie folgt sofort, dass \(\mathcal{E}_{c,d}(k)\) als Funktion von \(k\) monoton nicht steigend ist. Also besitzen die auslöschenden Startwerte die Form
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
Genau deshalb ist binäre Suche zulässig: Sobald ein \(k\) nicht mehr auslöscht, gilt das auch für alle größeren \(k\).
Setze
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
Da die Aktualisierung von Position \(h\) auf \(h+c \bmod s\) zugreift, bleibt jede Kopplung in derselben Restklasse modulo \(g\). Der große Zyklus zerfällt somit in \(g\) unabhängige kleinere Zyklen der Länge
\[ \frac{s}{g}=r_c+r_d. \]
Nur eine dieser Restklassen enthält den Anfangsimpuls; alle übrigen starten mit Null und bleiben für immer Null. Damit hängt die Schwelle nur vom gekürzten Paar ab:
\[ K(c,d)=K(r_c,r_d). \]
Nach der ggT-Reduktion berechnen die Programme keine vollständige zweidimensionale Tabelle. Stattdessen nutzen sie eine stärkere Strukturbeziehung und rekonstruieren die reduzierten Fälle aus eindimensionalen Familien.
Schreibe
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
Dann wird der reduzierte Wert durch
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1 \end{cases} \]
bestimmt. Fast alle benötigten Fälle werden also durch die Linie \(K(1,n)\) beschrieben; nur der Randfall \(r_d=1\) bleibt als eigene kleine Familie stehen.
Hier ist \(s=3\), also beginnt der Prozess mit \((0,0,k)\). Für \(k=3\) erhält man komprimiert
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
Der Startwert 3 löscht also aus.
Für \(k=4\) entsteht dagegen
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
Sobald \((1,1,1)\) erreicht ist, sind alle Koordinaten positiv, also ist Auslöschung unmöglich. Daher \(K(2,1)=3\) und damit
\[ G(2,1)=2\cdot 3+1=7. \]
Die C++-, Python- und Java-Implementierungen simulieren die In-Place-Rekursion für ein festes \((c,d,k)\) exakt. Neben dem Zustand selbst halten sie die Kopfposition und die Anzahl der Nullen fest. Daraus ergeben sich zwei exakte Abbruchkriterien: Alle Werte null bedeutet Auslöschung; keine Null mehr bedeutet, dass der Prozess im vorwärtsinvarianten positiven Bereich angekommen ist.
Jede Schwelle wird per Verdopplung und anschließender binärer Suche bestimmt. Für die Familie \(K_1(n)=K(1,n)\) verwenden die Implementierungen zusätzlich einen kubischen Prädiktor, der nur von \(n \bmod 8\) abhängt und das Startintervall der Suche nahe an den wahren Wert legt. Das beschleunigt die Berechnung, ändert aber die Antwort nicht.
Die Hauptarbeit ist die Tabelle \(K_1(1),\dots,K_1(239)\). C++ und Java berechnen sie parallel, Python benutzt mehrere Prozesse, falls möglich. Für die Randfamilie \(K(m,1)\) werden kleine Werte direkt berechnet; größere Werte werden aus derselben Verdichtung rekonstruiert und zusätzlich stichprobenartig gegen die direkte Dynamik geprüft.
Für jedes Paar \((c,d)\) wird zuerst mit dem ggT auf \((r_c,r_d)\) reduziert. Danach wird die passende Schwelle aus den vorberechneten Tabellen gelesen,
\[ G(c,d)=2K(r_c,r_d)+1 \]
gebildet und in die Gesamtsumme aufgenommen. Da das Endergebnis weit über den Bereich normaler Maschinenzahlen hinausgeht, wird die Summe mit Ganzzahlarithmetik beliebiger Präzision geführt.
Sei \(\tau(c,d,k)\) die Zahl elementarer Aktualisierungen, die ein Testlauf für \((c,d,k)\) bis zu einem seiner beiden exakten Abbruchkriterien benötigt. Dann kostet eine Schwellenbestimmung
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
weil Verdopplung und binäre Suche nur logarithmisch viele Testläufe auslösen.
Der größte Aufwand steckt in der Vorberechnung von \(K_1(1),\dots,K_1(239)\). Danach ist die doppelte Summe über alle \(160^2\) Paare billig: ein ggT, ein Tabellenzugriff und wenige Rechenschritte pro Paar. Der Speicherbedarf bleibt klein, denn eine Simulation speichert höchstens \(c+d\le 320\) Werte, und die vorberechneten Tabellen haben nur einige hundert Einträge.
Her \(1 \le c,d \le 160\) çifti için \(s=c+d\) alınır. Uzunluğu \(s\) olan bir çember üzerinde negatif olmayan tamsayılar vardır. Başlangıçta yalnızca tek bir konumda \(k\) değeri bulunur; sonra da taban alan, çevrimsel ve yerinde bir ortalama güncellemesi tekrar tekrar uygulanır. Temel nicelik \(K(c,d)\) olup, bu süreçte hâlâ tamamen sıfıra sönümlenen en büyük başlangıç değeridir.
\(K(c,d)\) bulunduğunda istenen ifade
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d) \]
olur. Doğrudan arama mümkün değildir; eşikler büyüktür. Çözüm, güncellemenin monoton yapısını, \(\gcd(c,d)\) ile gelen tam indirgemeyi ve indirgenmiş problemlerin tek boyutlu tablolara çökmesini kullanır.
Bu problem bir çevrim üzerinde tanımlı ayrık bir dinamik sistemdir. Asıl önemli olan şey, kullanılan gerçek tekrar bağıntısı, onun koruduğu bölgeler ve bunların ürettiği eşik yapısıdır.
Konumları \(0,1,\dots,s-1\) diye numaralandıralım ve durumu \(x=(x_0,\dots,x_{s-1})\) ile gösterelim. Başlangıç durumu
\[ x_{s-1}=k, \qquad x_i=0 \text{ for } i\ne s-1 \]
şeklindedir.
Her temel adımda yalnızca bir koordinat güncellenir. Güncel baş konumu \(h\) ise
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor \]
olur ve sonra baş \(h+1 \bmod s\) konumuna ilerler. \(s=c+d\) olduğu için aynı kural
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor \]
diye de yazılabilir. C++, Python ve Java uygulamalarının tam olarak simüle ettiği süreç budur. Güncelleme yerindedir; bu yüzden turun erken kısmında yazılan değerler aynı turun geç kısmında hemen kullanılabilir.
Yerel dönüşüm \((a,b)\mapsto \lfloor(a+b)/2\rfloor\), her iki girdide de monotondur. Bu nedenle \(k_1 \le k_2\) ise, aynı güncelleme sırası altında başlayan iki yörüngede bileşen bazında düzen sonsuza kadar korunur. Daha büyük başlangıç darbesi, daha küçük olanın altında bir durum üretemez.
Ayrıca iki önemli ileriye kapalı bölge vardır:
\[ x\equiv 0 \implies \text{sonraki bütün durumlar yine } 0, \]
ve
\[ x_i \ge 1 \text{ her } i \text{ için} \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
Dolayısıyla bütün koordinatlar pozitif olduktan sonra süreç artık tüm sıfıra inemez. Uygulamaların “tamamı sıfır” ya da “hiç sıfır kalmadı” durumlarında güvenle durmasının sebebi budur.
Bir başka basit invariant da şudur:
\[ 0 \le x_i \le k. \]
Hiçbir güncelleme negatif değer üretmez ve başlangıç darbesinin üstüne çıkmaz.
Aşağıdaki predikatı tanımlayalım:
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{başlangıç } k \text{ sonunda tüm sıfıra ulaşıyorsa},\\ 0, & \text{aksi halde.} \end{cases} \]
Monotonluk nedeniyle \(\mathcal{E}_{c,d}(k)\), \(k\)'ye göre artmayan bir fonksiyondur. O hâlde sönen başlangıç değerleri mutlaka bir başlangıç aralığı oluşturur:
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
İkili aramanın matematiksel dayanağı budur: bir \(k\) artık sönmüyorsa ondan büyük hiçbir değer de sönmez.
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g} \]
olsun. Güncelleme \(h\) konumunu \(h+c \bmod s\) ile eşlediği için etkileşimler her zaman aynı \(g\) artık sınıfı içinde kalır. Böylece uzun çevrim, her biri
\[ \frac{s}{g}=r_c+r_d \]
uzunluğunda olan \(g\) bağımsız alt çevrime ayrılır. Bu alt çevrimlerden yalnızca biri başlangıç darbesini içerir; diğerleri sıfırdan başlar ve sonsuza kadar sıfır kalır. Bu yüzden eşik yalnızca sadeleştirilmiş çifte bağlıdır:
\[ K(c,d)=K(r_c,r_d). \]
\(\gcd\) indirgemesinden sonra kod iki boyutlu tam bir tablo kurmaz. Bunun yerine daha güçlü bir yapısal ilişki kullanır ve bütün indirgenmiş durumları tek boyutlu ailelerden yeniden üretir.
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1) \]
olsun. O zaman çözücüde kullanılan formül
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1 \end{cases} \]
şeklindedir. Yani iki parametreli aile büyük ölçüde \(K(1,n)\) doğrusu üzerine çöker; yalnızca \(r_d=1\) olan sınır şeridi ayrı tutulur.
Burada \(s=3\) ve başlangıç durumu \((0,0,k)\)'dir. \(k=3\) için sıkıştırılmış iz
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0) \]
olur; yani 3 gerçekten söner.
\(k=4\) için ise
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1) \]
elde edilir. \((1,1,1)\) durumuna gelince bütün koordinatlar pozitiftir ve süreç artık sıfıra ulaşamaz. Demek ki \(K(2,1)=3\) ve buradan
\[ G(2,1)=2\cdot 3+1=7 \]
çıkar. Küçük örnek, genel problemin neden bir eşik aramasına dönüştüğünü açıkça gösterir.
C++, Python ve Java uygulamaları sabit bir \((c,d,k)\) için yerinde güncelleme sürecini tam olarak simüle eder. Durum vektörünün yanında baş konumu ve sıfır sayısı da tutulur. Bu sayaç iki kesin çıkış koşulu verir: tüm girişler sıfırsa sönüm gerçekleşmiştir; hiç sıfır kalmadıysa sistem ileriye kapalı pozitif bölgeye girmiştir.
Her eşik önce üst sınırı iki katına çıkararak çevrelenir, sonra ikili aramayla tam değere indirilir. \(K_1(n)=K(1,n)\) ailesi için uygulamalar ek olarak \(n \bmod 8\)'e bağlı sekiz parçalı kübik bir tahmin kullanır. Bu tahmin yalnızca ilk arama penceresini daraltır; doğruluğa etkisi yoktur.
Ana ön hesap \(K_1(1),\dots,K_1(239)\) tablosudur. C++ ve Java bunu iş parçacıklarıyla, Python ise mümkün olduğunda çoklu süreçlerle hesaplar. \(K(m,1)\) kolunda bazı küçük değerler doğrudan simülasyonla alınır; daha büyükler aynı yapısal çökmeden geri kurulur ve birkaç doğrudan kontrol ile doğrulanır.
Her \((c,d)\) çifti önce \(\gcd(c,d)\) ile sadeleştirilir. Ardından uygun eşik tablodan okunur,
\[ G(c,d)=2K(r_c,r_d)+1 \]
hesaplanır ve tüm \(160^2\) çiftler üzerinde toplanır. Sonucun makine tamsayısını aştığı için toplam keyfi duyarlıklı tamsayı aritmetiğiyle tutulur.
\(\tau(c,d,k)\), \((c,d,k)\) için yapılan bir test simülasyonunun iki kesin durma koşulundan birine ulaşana kadar kullandığı temel güncelleme sayısı olsun. Bir tek eşik sorgusunun maliyeti
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big) \]
olur; çünkü önce üst sınır genişletilir, sonra logaritmik sayıda ikili arama adımı uygulanır.
Asıl maliyet \(K_1(1),\dots,K_1(239)\) tablosunun ön hesabıdır. Bundan sonra \(c,d\le 160\) için yapılan son çift toplamı çok hafiftir: bir ebob, bir tablo erişimi ve birkaç aritmetik işlem yeterlidir. Bellek kullanımı küçüktür; tek bir simülasyon en fazla \(c+d\le 320\) tamsayı tutar, önceden hesaplanan tablolar da yalnızca birkaç yüz giriş içerir.
Para cada par \(1 \le c,d \le 160\), se toma \(s=c+d\). Sobre un ciclo de longitud \(s\) hay enteros no negativos. El estado inicial es un único impulso \(k\) en una posición, y después se aplica repetidamente una actualización cíclica, in-place y con redondeo hacia abajo. La cantidad central es \(K(c,d)\), el mayor valor inicial que todavía termina en el estado nulo.
Una vez conocido \(K(c,d)\), el problema pide
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
Buscar ese umbral por fuerza bruta sería demasiado caro. La solución usa la monotonía exacta de la recurrencia, una reducción por \(\gcd(c,d)\) y una reconstrucción adicional a partir de tablas unidimensionales.
El problema completo puede verse como un sistema dinámico discreto sobre un anillo. Lo importante es la recurrencia concreta, las regiones invariantes y la estructura de umbral que esas propiedades producen.
Numeramos las posiciones como \(0,1,\dots,s-1\), y escribimos el estado como \(x=(x_0,\dots,x_{s-1})\). El estado inicial es
\[ x_{s-1}=k, \qquad x_i=0 \text{ si } i\ne s-1. \]
En cada paso elemental cambia una sola coordenada. Si la cabeza actual está en \(h\), la actualización es
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
y luego la cabeza avanza a \(h+1 \bmod s\). Como \(s=c+d\), la misma regla también puede escribirse como
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor. \]
Ésa es exactamente la dinámica asíncrona que implementan las tres versiones.
La transformación local \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) es monótona en ambos argumentos. Por tanto, si \(k_1 \le k_2\), entonces al ejecutar el mismo calendario de actualizaciones se preserva para siempre el orden componente a componente. Un impulso inicial mayor nunca puede generar una trayectoria menor.
Además hay dos regiones invariantes hacia delante:
\[ x\equiv 0 \implies \text{todos los estados futuros siguen siendo } 0, \]
y
\[ x_i \ge 1 \text{ para todo } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
Así, una vez que no queda ningún cero, la extinción ya es imposible. Por eso las implementaciones pueden detenerse exactamente cuando el estado es totalmente nulo o totalmente positivo.
También se conserva el acotamiento
\[ 0 \le x_i \le k, \]
porque ningún paso crea valores negativos ni supera el impulso inicial.
Definimos
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{si la trayectoria iniciada en } k \text{ alcanza el estado nulo},\\ 0, & \text{en caso contrario.} \end{cases} \]
La monotonía implica que \(\mathcal{E}_{c,d}(k)\) es no creciente en \(k\). Por ello, los valores iniciales que se extinguen forman un prefijo:
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
Ésa es la razón matemática por la que la búsqueda binaria funciona.
Sea
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
Como la posición \(h\) siempre interactúa con \(h+c \bmod s\), toda dependencia conserva la clase residual módulo \(g\). En consecuencia, el ciclo grande se separa en \(g\) subciclos independientes, cada uno de longitud
\[ \frac{s}{g}=r_c+r_d. \]
Sólo uno de ellos contiene el impulso inicial; los otros comienzan en cero y permanecen en cero. Por tanto, el umbral depende únicamente del par reducido:
\[ K(c,d)=K(r_c,r_d). \]
Después de dividir por el máximo común divisor, la solución no construye una tabla completa en dos dimensiones. En su lugar usa una relación estructural más fuerte y reconstruye todos los casos a partir de familias de una sola variable.
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
El valor reducido utilizado por la implementación es
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1. \end{cases} \]
En otras palabras, casi todos los pares reducidos quedan determinados por la recta \(K(1,n)\), con una pequeña franja especial cuando \(r_d=1\).
Aquí \(s=3\), así que el estado inicial es \((0,0,k)\). Para \(k=3\), una traza comprimida es
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
Luego \(k=3\) sí se extingue.
Con \(k=4\), en cambio, aparece
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
Una vez alcanzado \((1,1,1)\), todas las coordenadas son positivas y la extinción ya no puede ocurrir. Por eso \(K(2,1)=3\), y entonces
\[ G(2,1)=2\cdot 3+1=7. \]
Las implementaciones en C++, Python y Java simulan exactamente la recurrencia in-place para un triple fijo \((c,d,k)\). Mantienen el estado cíclico, la posición de la cabeza y el número de entradas nulas. Ese contador proporciona dos condiciones de parada exactas: todo cero certifica extinción y cero ceros certifica que ya se entró en la región positiva, desde la cual no es posible volver al estado nulo.
Cada umbral se obtiene expandiendo un intervalo por duplicación y después aplicando búsqueda binaria. Para la familia \(K_1(n)=K(1,n)\), la implementación usa además un predictor cúbico de ocho clases según \(n \bmod 8\), cuyo único objetivo es centrar mejor la ventana inicial de búsqueda.
La principal precomputación es la tabla \(K_1(1),\dots,K_1(239)\). C++ y Java la paralelizan; Python usa varios procesos si el entorno lo permite y, si no, vuelve a un recorrido secuencial. En la rama \(K(m,1)\), algunos valores pequeños se calculan directamente y los mayores se reconstruyen con la misma reducción estructural, acompañados por comprobaciones directas en puntos representativos.
Para cada par \((c,d)\), primero se reduce a \((r_c,r_d)\) dividiendo por \(\gcd(c,d)\). Después se recupera el umbral apropiado desde las tablas ya calculadas, se forma
\[ G(c,d)=2K(r_c,r_d)+1, \]
y se acumula sobre los \(160^2\) pares. El total final se guarda con aritmética entera de precisión arbitraria.
Sea \(\tau(c,d,k)\) el número de actualizaciones elementales realizadas antes de que la prueba para \((c,d,k)\) alcance una de sus dos condiciones exactas de parada. Entonces el coste de un solo umbral es
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
porque el esquema de duplicación y búsqueda binaria necesita sólo un número logarítmico de simulaciones.
El trabajo dominante es la precomputación de \(K_1(1),\dots,K_1(239)\). Después de eso, la suma final sobre todos los pares es barata: un mcd, una consulta de tabla y unas pocas operaciones aritméticas por caso. La memoria también es pequeña: una simulación usa a lo sumo \(c+d\le 320\) enteros y las tablas precalculadas contienen sólo unos cientos de entradas.
对每个 \(1 \le c,d \le 160\)，令 \(s=c+d\)。在长度为 \(s\) 的环上放置非负整数。初始时只有一个位置带有脉冲 \(k\)，其余位置全为 0；随后反复执行一次带下取整的循环原地平均更新。核心量 \(K(c,d)\) 表示仍然会最终衰减到全零状态的最大初始值。
一旦知道 \(K(c,d)\)，题目要求的就是
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
如果对每个参数都暴力搜索阈值，代价会非常高。真正可行的做法来自三个问题特有的结构：更新规则的单调性、按 \(\gcd(c,d)\) 的精确约化，以及约化后再压缩成一维阈值表。
这个问题本质上是一个定义在环上的离散动力系统。需要抓住的不是通用模板，而是这里的真实递推、真实不变量以及由此产生的阈值结构。
把环上的位置记为 \(0,1,\dots,s-1\)，状态写成 \(x=(x_0,\dots,x_{s-1})\)。初始状态是
\[ x_{s-1}=k, \qquad x_i=0 \text{，当 } i\ne s-1. \]
每个基本步骤只更新一个坐标。若当前头指针在 \(h\)，则执行
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
然后头指针前进到 \(h+1 \bmod s\)。因为 \(s=c+d\)，同一条规则也可以写成
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor. \]
三种语言的实现模拟的正是这个异步、原地的递推过程。所谓“原地”，就是本轮前面位置刚写出的值，后面位置可以立刻读到。
局部变换 \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) 对两个输入都是单调的。因此若两个初始脉冲满足 \(k_1 \le k_2\)，并且按同一更新顺序推进，那么之后任意时刻都保持分量上的偏序。也就是说，更大的初始脉冲不可能在后续某一步突然变得比更小的脉冲还“小”。
另外，这个系统有两个非常关键的前向不变区域：
\[ x\equiv 0 \implies \text{以后永远保持全零}, \]
以及
\[ x_i \ge 1 \text{ 对所有 } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
第二条说明：一旦状态中再也没有 0，就不可能回到全零。也正因为如此，程序把“全部为零”和“一个零也没有”作为两个完全可靠的停止判据。
还存在一个简单但有用的界：
\[ 0 \le x_i \le k. \]
更新既不会产生负数，也不会把任何分量抬到初始脉冲之上。
定义灭绝谓词
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{如果从 } k \text{ 出发最终到达全零状态},\\ 0, & \text{否则。} \end{cases} \]
由于前面证明了保序性，\(\mathcal{E}_{c,d}(k)\) 关于 \(k\) 必然是单调不增的。因此会灭绝的初始值一定构成一个前缀区间：
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
这正是二分搜索成立的数学原因：一旦某个 \(k\) 已经不会灭绝，比它更大的初值也都不会灭绝。
令
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
由于位置 \(h\) 的更新总是读取 \(h+c \bmod s\)，所以相互依赖的两个位置必然属于同一个模 \(g\) 的剩余类。于是长度为 \(s\) 的大环会分裂成 \(g\) 个互不相干的小环，每个小环长度都是
\[ \frac{s}{g}=r_c+r_d. \]
初始脉冲只落在其中一个剩余类里，其余 \(g-1\) 个小环从 0 开始，也永远保持 0。于是阈值只取决于约化后的参数：
\[ K(c,d)=K(r_c,r_d). \]
这一步完全精确，不是经验近似；它解释了为什么最终求和时总是先把 \((c,d)\) 除以它们的最大公约数。
在做完 \(\gcd\) 约化之后，程序并没有去建立一张完整的二维阈值表，而是进一步利用了更强的结构关系，把约化后的参数重新映射到一维家族。
记
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
那么实现中使用的约化公式为
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1. \end{cases} \]
这意味着大多数约化后的二元问题都可以沿着直线 \(K(1,n)\) 解决，只在 \(r_d=1\) 这条边界上保留一小段单独处理的家族。
此时 \(s=3\)，初始状态为 \((0,0,k)\)。当 \(k=3\) 时，可以压缩写成
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
所以 \(k=3\) 确实会灭绝。
但当 \(k=4\) 时，轨迹会变成
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
一旦到达 \((1,1,1)\)，所有分量都严格为正，之后就不可能再回到全零。因此 \(K(2,1)=3\)，于是
\[ G(2,1)=2\cdot 3+1=7. \]
这个小例子直接展示了本题的本质：动态过程最终被保序性转化成一个精确的阈值搜索问题。
C++、Python 和 Java 实现都会对固定的 \((c,d,k)\) 精确模拟这条原地递推。程序保存当前环状状态、头指针位置，以及状态中 0 的个数。这个计数器给出两个严格可靠的停止条件：如果全部为 0，说明已经灭绝；如果一个 0 都没有，说明系统进入了之后不可能再灭绝的全正区域。
每个阈值都通过“先倍增找上界，再二分锁定答案”的方式求出。对于家族 \(K_1(n)=K(1,n)\)，实现还加入了一个按 \(n \bmod 8\) 分成八类的三次预测器，用来把搜索窗口放到真值附近。这个预测器只影响速度，不影响正确性。
最主要的预计算工作是表 \(K_1(1),\dots,K_1(239)\)。C++ 和 Java 会并行构造这张表；Python 则在环境允许时使用多进程，否则退回串行求值。至于 \(K(m,1)\) 这一支，一些小参数直接做精确模拟，较大的参数则借助同一条结构塌缩关系重建，并用几个代表性点进行直接校验。
对每个 \((c,d)\)，程序先除以 \(\gcd(c,d)\) 得到 \((r_c,r_d)\)，再从预计算表中取出相应阈值，形成
\[ G(c,d)=2K(r_c,r_d)+1, \]
最后对全部 \(160^2\) 个参数对求和。由于总和远超普通机器整数范围，因此实现使用任意精度整数保存最终结果。
记 \(\tau(c,d,k)\) 为对 \((c,d,k)\) 进行一次灭绝测试时，直到触发两个精确停止条件之一所需的基本更新次数。那么单个阈值查询的代价是
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
因为倍增定界与二分搜索只会调用对数级别的测试次数。
总体上最重的部分是 \(K_1(1),\dots,K_1(239)\) 的预计算。完成之后，最终的 \(160\times160\) 求和非常轻：每一项只需要一次 \(\gcd\)、一次表查找和少量整数运算。空间使用也很小；单次模拟最多保存 \(c+d\le 320\) 个整数，而预计算表也只有几百个条目。
Для каждой пары \(1 \le c,d \le 160\) положим \(s=c+d\). На цикле длины \(s\) расположены неотрицательные целые числа. В начальный момент только одна позиция содержит импульс \(k\), а затем многократно выполняется циклическое in-place-усреднение с округлением вниз. Главная величина задачи — \(K(c,d)\), то есть наибольшее начальное значение, которое всё ещё приводит траекторию к нулевому состоянию.
После нахождения \(K(c,d)\) нужно вычислить
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
Лобовой перебор всех стартовых значений слишком дорог. Решение опирается на монотонность обновления, точную редукцию по \(\gcd(c,d)\) и дальнейшее свёртывание reduced-пар в одномерные таблицы порогов.
Перед нами дискретная динамическая система на цикле. Ключевыми оказываются конкретная рекурсия, её инвариантные области и пороговая структура, которая из них следует.
Пронумеруем позиции как \(0,1,\dots,s-1\) и обозначим состояние через \(x=(x_0,\dots,x_{s-1})\). Начальное состояние имеет вид
\[ x_{s-1}=k, \qquad x_i=0 \text{ при } i\ne s-1. \]
На каждом элементарном шаге меняется только одна координата. Если текущая головная позиция равна \(h\), то выполняется
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
после чего голова переходит в \(h+1 \bmod s\). Так как \(s=c+d\), ту же формулу можно записать и как
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor. \]
Именно эту асинхронную in-place-динамику реализуют версии на C++, Python и Java.
Локальное преобразование \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) монотонно по каждому аргументу. Поэтому если \(k_1 \le k_2\), то при одинаковом расписании обновлений покоординатный порядок между двумя траекториями сохраняется навсегда. Больший стартовый импульс не может породить траекторию ниже меньшего.
Кроме того, есть две важные области, инвариантные вперёд:
\[ x\equiv 0 \implies \text{все будущие состояния остаются нулевыми}, \]
и
\[ x_i \ge 1 \text{ для всех } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
Следовательно, если нулей больше не осталось, то в нулевое состояние система уже не вернётся. Именно поэтому реализации имеют два точных условия остановки: все нули или ни одного нуля.
Полезен и ещё один инвариант:
\[ 0 \le x_i \le k. \]
Значения не могут стать отрицательными и не могут превысить начальный импульс.
Введём предикат
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{если траектория со стартом } k \text{ достигает нулевого состояния},\\ 0, & \text{иначе.} \end{cases} \]
Из монотонности следует, что \(\mathcal{E}_{c,d}(k)\) не возрастает по \(k\). Значит, все затухающие старты образуют начальный интервал
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
Это и есть математическое обоснование двоичного поиска: как только некоторое \(k\) перестало затухать, все большие значения тоже перестают затухать.
Положим
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
Так как обновление позиции \(h\) читает значение из \(h+c \bmod s\), любая зависимость сохраняет класс вычетов по модулю \(g\). Поэтому большой цикл распадается на \(g\) независимых малых циклов длины
\[ \frac{s}{g}=r_c+r_d. \]
Начальный импульс находится только в одном таком классе вычетов; остальные стартуют с нуля и навсегда остаются нулевыми. Значит, порог зависит только от сокращённой пары:
\[ K(c,d)=K(r_c,r_d). \]
После редукции по НОД реализации не строят полную двумерную таблицу. Вместо этого они используют более сильную структурную связь и восстанавливают все reduced-случаи из одномерных семейств.
Обозначим
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
Тогда используемая формула такова:
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1. \end{cases} \]
Тем самым почти все reduced-пары сводятся к прямой \(K(1,n)\), а особый случай \(r_d=1\) остаётся небольшой отдельной полосой.
Здесь \(s=3\), значит начальное состояние равно \((0,0,k)\). Для \(k=3\) можно сжато записать траекторию так:
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
Следовательно, \(k=3\) действительно затухает.
Для \(k=4\) получаем
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
После достижения \((1,1,1)\) все координаты положительны, а значит возврат к нулю уже невозможен. Отсюда \(K(2,1)=3\) и
\[ G(2,1)=2\cdot 3+1=7. \]
Реализации на C++, Python и Java точно моделируют in-place-рекурсию для фиксированного \((c,d,k)\). Они хранят текущее циклическое состояние, позицию головы и число нулевых ячеек. Этот счётчик даёт два строгих условия остановки: все нули означают, что затухание произошло; отсутствие нулей означает попадание в положительную область, из которой нулевое состояние уже недостижимо.
Каждый порог находится одинаково: сначала верхняя граница расширяется удвоением, затем между последним затухающим и первым незатухающим значением запускается двоичный поиск. Для семейства \(K_1(n)=K(1,n)\) дополнительно используется кубический предиктор по классу \(n \bmod 8\), который помогает сразу выбрать окно поиска рядом с истинным ответом. На корректность это не влияет, меняется только скорость.
Основная предвычисляемая таблица — это \(K_1(1),\dots,K_1(239)\). C++ и Java строят её параллельно, Python использует несколько процессов при наличии такой возможности и иначе переходит к последовательному режиму. Для ветви \(K(m,1)\) часть малых значений вычисляется напрямую, а большие значения восстанавливаются той же структурной редукцией и проверяются на нескольких контрольных точках прямым моделированием.
Для каждой пары \((c,d)\) программа сначала делит её на \(\gcd(c,d)\), получая \((r_c,r_d)\). Затем из готовых таблиц извлекается нужный порог, формируется
\[ G(c,d)=2K(r_c,r_d)+1, \]
и результат добавляется к общей сумме по всем \(160^2\) парам. Так как итог намного больше машинного слова, для накопления используется целая арифметика произвольной точности.
Пусть \(\tau(c,d,k)\) обозначает число элементарных обновлений до тех пор, пока тест для \((c,d,k)\) не достигнет одного из двух точных условий остановки. Тогда вычисление одного порога имеет стоимость
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
поскольку схема с удвоением и двоичным поиском требует лишь логарифмического числа запусков симуляции.
Главный объём работы приходится на предвычисление \(K_1(1),\dots,K_1(239)\). После этого окончательная сумма по всем \(c,d\le 160\) вычисляется дёшево: один НОД, один табличный доступ и несколько арифметических операций на пару. Память тоже мала: одна симуляция хранит не более \(c+d\le 320\) целых значений, а сами таблицы содержат лишь несколько сотен элементов.
لكل زوج \(1 \le c,d \le 160\) نضع \(s=c+d\). لدينا أعداد صحيحة غير سالبة موزعة على دورة طولها \(s\). تبدأ العملية بنبضة وحيدة مقدارها \(k\) في موضع واحد، ثم نكرر تحديثًا دائريًا موضعيًا يقوم بأخذ متوسط صحيح مع تقريب إلى الأسفل. الكمية الأساسية هي \(K(c,d)\)، أي أكبر قيمة ابتدائية ما تزال تنتهي في الحالة الصفرية الكاملة.
بعد معرفة \(K(c,d)\)، يصبح المطلوب هو
\[ G(c,d)=2K(c,d)+1, \qquad \sum_{c=1}^{160}\sum_{d=1}^{160} G(c,d). \]
البحث المباشر عن هذه العتبات مكلف جدًا. الحل يعتمد على ثلاث حقائق خاصة بهذه المسألة: رتابة قاعدة التحديث، والاختزال الدقيق بواسطة \(\gcd(c,d)\)، ثم ضغط الأزواج المختزلة إلى جداول أحادية البعد.
جوهر المسألة هو نظام ديناميكي متقطع على حلقة. ما نحتاجه هنا ليس قالبًا عامًا، بل التكرار الحقيقي الذي تستخدمه الحلول، والمناطق الثابتة التي يحافظ عليها، وبنية العتبة الناتجة عن ذلك.
نرقم المواضع \(0,1,\dots,s-1\)، ونكتب الحالة على صورة \(x=(x_0,\dots,x_{s-1})\). الحالة الابتدائية هي
\[ x_{s-1}=k, \qquad x_i=0 \text{ for } i\ne s-1. \]
في كل خطوة أولية يتغير عنصر واحد فقط. إذا كان موضع الرأس الحالي هو \(h\)، فإن التحديث هو
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h-d \bmod s}}{2} \right\rfloor, \]
ثم ينتقل الرأس إلى \(h+1 \bmod s\). وبما أن \(s=c+d\)، يمكن كتابة القاعدة نفسها أيضًا بالشكل
\[ x_h \leftarrow \left\lfloor \frac{x_h + x_{h+c \bmod s}}{2} \right\rfloor. \]
هذه هي الديناميكا غير المتزامنة والموضعية التي تنفذها الشيفرات في اللغات الثلاث. وكونها موضعية يعني أن القيمة التي تُكتب في بداية الدورة يمكن أن تقرأ فورًا في بقية الدورة نفسها.
التحويل المحلي \((a,b)\mapsto \lfloor(a+b)/2\rfloor\) رتيب في كل من المدخلين. لذلك إذا كان \(k_1 \le k_2\)، وشغلنا المسارين تحت ترتيب التحديث نفسه، فإن الترتيب المركبي بين الحالتين يبقى محفوظًا إلى الأبد. أي إن النبضة الأكبر لا يمكن أن تنتج لاحقًا حالة أصغر من الحالة الناتجة عن نبضة أصغر.
كذلك توجد منطقتان ثابتتان إلى الأمام:
\[ x\equiv 0 \implies x \text{ stays zero forever}, \]
و
\[ x_i \ge 1 \text{ for all } i \implies \left\lfloor \frac{x_i+x_j}{2} \right\rfloor \ge 1. \]
إذن متى ما أصبحت كل المداخل موجبة، صار الوصول إلى الحالة الصفرية مستحيلًا. ولهذا تتوقف التطبيقات بدقة عند حالتين فقط: إما أن تصبح كل القيم صفرًا، أو يختفي الصفر تمامًا من الحالة.
وهناك ثابت بسيط آخر:
\[ 0 \le x_i \le k. \]
فلا توجد خطوة قادرة على إنتاج قيمة سالبة أو قيمة أكبر من النبضة الابتدائية.
نعرّف دالة الانقراض
\[ \mathcal{E}_{c,d}(k)= \begin{cases} 1, & \text{if the trajectory from } k \text{ reaches } 0,\\ 0, & \text{otherwise.} \end{cases} \]
من الرتابة نستنتج أن \(\mathcal{E}_{c,d}(k)\) غير متزايدة مع \(k\). لذلك تشكل القيم الابتدائية المنقرضة فترة بادئة من الشكل
\[ \{k\ge 0 : \mathcal{E}_{c,d}(k)=1\}=\{0,1,\dots,K(c,d)\}. \]
وهذا هو السبب الرياضي الذي يجعل البحث الثنائي صالحًا هنا: إذا فشلت قيمة ما في الانقراض، فكل قيمة أكبر منها ستفشل كذلك.
لنضع
\[ g=\gcd(c,d), \qquad r_c=\frac{c}{g}, \qquad r_d=\frac{d}{g}. \]
بما أن تحديث الموضع \(h\) يقرأ دائمًا من الموضع \(h+c \bmod s\)، فإن أي اعتماد يبقى داخل الفئة الباقية نفسها modulo \(g\). لذا تنقسم الدورة الكبيرة إلى \(g\) دورات أصغر مستقلة، طول كل منها
\[ \frac{s}{g}=r_c+r_d. \]
النبضة الابتدائية تقع في فئة باقية واحدة فقط، بينما تبدأ الفئات الأخرى من الصفر وتبقى صفرية إلى الأبد. ومن ثم فإن العتبة تعتمد فقط على الزوج المختزل:
\[ K(c,d)=K(r_c,r_d). \]
بعد الاختزال بالـ \(\gcd\)، لا تبني الحلول جدولًا ثنائي الأبعاد كاملًا. بدلًا من ذلك تستخدم علاقة بنيوية أقوى تعيد كل الأزواج المختزلة إلى عائلات أحادية البعد.
لنكتب
\[ K_1(n)=K(1,n), \qquad K_{d=1}(m)=K(m,1). \]
وعندها تكون الصيغة المستعملة هي
\[ K(r_c,r_d)= \begin{cases} K_{d=1}(r_c), & r_d=1,\\ K_1\!\left(r_d+\left\lfloor\frac{r_c-1}{2}\right\rfloor\right), & r_d>1. \end{cases} \]
أي إن معظم الأزواج المختزلة يحددها الخط \(K(1,n)\)، مع شريط صغير خاص عندما \(r_d=1\).
في هذه الحالة \(s=3\)، وبالتالي تبدأ العملية من \((0,0,k)\). عندما \(k=3\)، يمكن تلخيص المسار كالتالي:
\[ (0,0,3)\to(1,0,3)\to(1,0,1)\to(1,0,0)\to(0,0,0). \]
إذن القيمة 3 تنقرض فعلًا.
أما عندما \(k=4\)، فنحصل على
\[ (0,0,4)\to(2,0,4)\to(2,1,4)\to(2,1,2)\to(2,1,1)\to(1,1,1). \]
بمجرد الوصول إلى \((1,1,1)\)، تصبح كل المركبات موجبة، وعندها يستحيل العودة إلى الحالة الصفرية. لذلك \(K(2,1)=3\)، ومن ثم
\[ G(2,1)=2\cdot 3+1=7. \]
تنفذ تطبيقات C++ وPython وJava التكرار الموضعي بدقة لثلاثية ثابتة \((c,d,k)\). وهي تحتفظ بالحالة الدائرية، وموضع الرأس، وعدد الخانات الصفرية. هذا العداد يعطي شرطي توقف دقيقين: إذا أصبحت كل القيم صفرًا فقد تحقق الانقراض، وإذا اختفى الصفر تمامًا فقد دخل النظام إلى المنطقة الموجبة التي يستحيل منها الوصول إلى الصفر.
تُحسب كل عتبة عبر توسيع الحد الأعلى تدريجيًا بالمضاعفة، ثم تطبيق البحث الثنائي بين آخر قيمة منقرضة وأول قيمة غير منقرضة. ولعائلة \(K_1(n)=K(1,n)\) تضيف الحلول مُقدّرًا تكعيبيًا من ثماني فئات يعتمد على \(n \bmod 8\)، هدفه فقط وضع نافذة البحث الابتدائية قرب الجواب الحقيقي.
أهم جزء في التهيئة المسبقة هو الجدول \(K_1(1),\dots,K_1(239)\). نسختا C++ وJava تحسبانه على التوازي، بينما تستخدم نسخة Python عدة عمليات عندما تسمح البيئة بذلك، وإلا تعود إلى التنفيذ التسلسلي. أما فرع \(K(m,1)\) فتُحسب بعض القيم الصغيرة فيه مباشرة، ثم تُعاد القيم الأكبر من العلاقة البنيوية نفسها مع نقاط تحقق مباشرة لضمان السلامة.
لكل زوج \((c,d)\)، يبدأ التنفيذ باختزاله إلى \((r_c,r_d)\) بقسمة الطرفين على \(\gcd(c,d)\). ثم يسترجع العتبة المناسبة من الجداول المحسوبة مسبقًا، ويكوّن
\[ G(c,d)=2K(r_c,r_d)+1, \]
ويجمع هذه القيمة على جميع الأزواج وعددها \(160^2\). وبما أن الناتج النهائي أكبر بكثير من سعة الأعداد الصحيحة العادية، يُحفظ المجموع باستخدام حساب صحيح ذي دقة غير محدودة.
لتكن \(\tau(c,d,k)\) عدد التحديثات الأولية اللازمة حتى يصل اختبار \((c,d,k)\) إلى أحد شرطي التوقف الدقيقين. عندئذ تكون كلفة حساب عتبة واحدة
\[ O\!\big(\tau(c,d,\cdot)\log K(c,d)\big), \]
لأن التوسيع بالمضاعفة ثم البحث الثنائي يتطلبان عددًا لوغاريتميًا فقط من اختبارات الانقراض.
الجزء المهيمن في الزمن هو بناء الجدول \(K_1(1),\dots,K_1(239)\). بعد اكتمال ذلك، تصبح عملية الجمع على جميع الأزواج خفيفة جدًا: حساب \(\gcd\)، وقراءة من جدول، وبضع عمليات حسابية لكل زوج. أما الذاكرة فتبقى صغيرة؛ فكل محاكاة تحتاج في أقصى الأحوال إلى \(c+d\le 320\) عددًا صحيحًا، والجداول المحسوبة مسبقًا لا تتجاوز بضع مئات من المدخلات.