The process starts with \(n\) stones at position \(0\). Positions are then processed in increasing order. If the current position \(i\) contains \(m\) stones, one singleton is left behind exactly when \(m\) is odd; in all cases \(\lfloor m/2\rfloor\) stones are sent to \(i+1\) and another \(\lfloor m/2\rfloor\) stones are sent to \(i+3\).
Only the positions where the current pile was odd matter for this problem. A singleton is lonely when no other singleton is within distance \(2\), so a sad integer is one whose singleton positions are pairwise separated by at least \(3\). The function \(S(k)\) asks for the sum of all sad starting values whose complete singleton set is contained in \(0\le i\lt k\). The target is \(S(80)\), and the problem gives the checks \(S(14)=159\) and \(S(30)=33438\).
The main challenge is that many starting values do not terminate. Even when the process keeps moving stones forever, it can still leave only finitely many singleton positions. So the solution cannot rely on simulating until all stones disappear; it must characterize the finite parity trace left by the process.
At each position the process removes pairs of stones and turns each pair at \(i\) into one stone at \(i+1\) and one stone at \(i+3\). The possible leftover digit at \(i\) is therefore only \(0\) or \(1\). This is analogous to carrying in a positional numeral system, except the carry rule is unusual:
$$2\cdot \text{position }i \quad\longrightarrow\quad \text{position }(i+1)+\text{position }(i+3).$$
If \(s_i\in\{0,1\}\) records whether a singleton was left at \(i\), then the process deterministically normalizes the starting pile \(n\) into a digit sequence \(s_0,s_1,s_2,\dots\). The sadness condition is then a condition on the support of this digit sequence.
Attach a formal weight \(x^i\) to position \(i\). For the carry rule to preserve weight, one pair at position \(i\) must have the same value as the two carried stones:
$$2x^i=x^{i+1}+x^{i+3}.$$
After division by \(x^i\), this becomes
$$x^3+x-2=0.$$
The polynomial factors as
$$x^3+x-2=(x-1)(x^2+x+2).$$
The factor \(x-1\) only tracks total mass, which is not enough here because the process may continue forever while leaving finitely many singletons. The useful finite trace is captured by the quadratic factor, so the implementation works in the ring where
$$x^2+x+2=0,\qquad\text{equivalently}\qquad x^2=-x-2.$$
Modulo \(x^2+x+2\), every power has the form
$$x^i=a_i+b_i x.$$
The first two values are \(x^0=1\) and \(x^1=x\). If \(x^{i-1}=a+b x\), then
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
Thus the code stores only two integers per position and advances by
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
For a finite singleton set \(P\), define
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
If \(P\) is the complete finite singleton set for some starting value \(n\), then its value in this quadratic quotient must equal the initial value \(n\), which has no \(x\)-part. Therefore the required algebraic test is
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
The left-to-right process is deterministic: once \(n\) is fixed, the parity digit \(s_i\) and the outgoing carry from position \(i\) are fixed. Conversely, a finite digit set \(P\) whose quadratic value is a positive integer is a valid finite trace for that integer under this carrying rule. The program uses this as a bijection between sad starting values counted by \(S(k)\) and finite subsets \(P\subseteq\{0,\dots,k-1\}\) satisfying the algebraic test and the loneliness gap.
This is also why the final answer is a sum of values \(A(P)\), not a count of sets. Each accepted set \(P\) represents one starting value \(n=A(P)\), and \(S(k)\) asks for the sum of those starting values.
A finite set \(P\) of singleton positions is lonely exactly when
$$|i-j|\ge 3\qquad\text{for all distinct }i,j\in P.$$
Equivalently, in the path graph on positions \(0,1,\dots,k-1\), where vertices at distance \(1\) or \(2\) conflict, \(P\) is an independent set. The problem has now become a finite combinatorial enumeration: list gap-\(3\) subsets, reduce their algebraic value to \(A+Bx\), and retain only positive integer values with \(B=0\).
The examples fall out directly. \(\{0\}\) gives \(1\). The set \(\{2,5,8,13\}\) gives \(68\), and \(\{1,13\}\) gives \(90\). These are the sad contributions below \(k=14\), so \(S(14)=1+68+90=159\).
Let \(F(t)\) be the number of subsets of \(\{0,\dots,t-1\}\) with mutual distance at least \(3\). Looking at the last position gives
$$F(t)=F(t-1)+F(t-3).$$
The term \(F(t-1)\) covers subsets not using the last position; the term \(F(t-3)\) covers subsets using it, because the previous two positions are then forbidden. For \(t=80\), this recurrence already gives \(25058735850088\) candidate subsets. That is far beyond direct enumeration.
Splitting at \(m=\lfloor k/2\rfloor\) changes the scale. For \(k=80\), each half has length \(40\), and the number of valid half-subsets is only \(F(40)=5736961\). Millions of states are manageable; tens of trillions are not.
Write the left-half value as \(A_L+B_Lx\) and the right-half value as \(A_R+B_Rx\). The union represents a positive integer exactly when
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
So the right half only needs to be searchable by coefficient \(B_R\). For each left subset, the required right coefficient is \(-B_L\), and every compatible right subset with that coefficient contributes the starting value \(A_L+A_R\).
The C++ implementation stores right entries sorted by coefficient and keeps prefix sums of their constants. That allows it to support even the general case where many right subsets have the same coefficient: binary search locates the matching block, and a second binary search discards entries whose total constant is not positive. The Python and Java ports use a lighter coefficient-to-constant table because, for the \(k\le80\) instances used here, the right coefficients are unique inside each boundary class.
The only missing condition after splitting is the distance rule across the cut. A left subset ending near \(m\) can conflict with a right subset beginning near \(m\). The code records exactly the information needed for this decision.
For the left half, the category is
$$0:\text{ no selected point at }m-2\text{ or }m-1,\qquad 1:\text{ last}=m-2,\qquad 2:\text{ last}=m-1.$$
For the right half, the category is
$$0:\text{ no selected point at }m\text{ or }m+1,\qquad 1:\text{ first}=m+1,\qquad 2:\text{ first}=m.$$
If the left category is \(0\), there is no left-side boundary conflict. If it is \(1\), only right category \(2\) is too close. If it is \(2\), both \(m\) and \(m+1\) are too close, so only right category \(0\) is allowed. This three-by-three compatibility rule is exactly the cross-boundary form of \(|i-j|\ge3\).
build_powers constructs the pairs \((a_i,b_i)\) for \(x^i=a_i+b_i x\). evaluate_positions sums those pairs for a proposed singleton set. singleton_positions directly simulates the stone process for small checks, which verifies both the algebraic representation and the interpretation of the singleton trace.
enumerate_right recursively enumerates all right-half gap-\(3\) subsets and places them into the three boundary buckets. Each stored entry contains the reduced coefficient and constant. build_left_tasks creates shallow left prefixes; the C++ version uses them to distribute the deeper left search across worker threads.
combine_left_dfs finishes each left subset, computes its boundary category, and queries only compatible right buckets. A match is accepted when the coefficients cancel and the constant sum is positive. That positive constant is added to the answer because it is the represented starting value.
The checkpoint suite verifies the known traces for \(n=1\), \(n=68\), and \(n=90\), then verifies \(S(14)=159\) and \(S(30)=33438\). Only after those checks does the program evaluate \(S(80)\).
The unsplit search would examine \(F(k)\) gap-valid subsets, which is not feasible for \(k=80\). The meet-in-the-middle method stores \(O(F(k/2))\) right-half states and performs \(O(F(k/2))\) left-half searches.
In the sorted-table C++ version, right-table construction costs \(O(F(k/2)\log F(k/2))\), and each completed left subset performs a constant number of binary-search lookups. The map-based Python and Java ports have expected \(O(F(k/2))\) table construction and expected constant-time lookups for the actual \(k\le80\) range. Memory usage is \(O(F(k/2))\).
Der Prozess beginnt mit \(n\) Steinen an Position \(0\). Danach werden die Positionen in aufsteigender Reihenfolge verarbeitet. Befinden sich an Position \(i\) genau \(m\) Steine, dann bleibt genau dann ein einzelner Stein zurueck, wenn \(m\) ungerade ist; anschliessend werden \(\lfloor m/2\rfloor\) Steine nach \(i+1\) und weitere \(\lfloor m/2\rfloor\) Steine nach \(i+3\) geschickt.
Fuer diese Aufgabe zaehlen nur die Positionen, an denen der aktuelle Haufen ungerade war. Ein einzelner Stein ist einsam, wenn kein anderer einzelner Stein in Abstand \(1\) oder \(2\) liegt. Ein sad-Startwert ist also ein Startwert, dessen Singleton-Positionen paarweise Abstand mindestens \(3\) haben. \(S(k)\) summiert alle solchen Startwerte, deren vollstaendige Singleton-Menge in \(0\le i\lt k\) liegt. Gesucht ist \(S(80)\), mit den Kontrollen \(S(14)=159\) und \(S(30)=33438\).
Die Schwierigkeit ist, dass der Prozess fuer viele Startwerte nicht terminiert. Er kann unendlich viele Steine weiter nach rechts tragen und trotzdem nur endlich viele Singleton-Positionen hinterlassen. Eine Loesung darf daher nicht auf das Verschwinden aller Steine warten; sie muss die endliche Paritaetsspur des Prozesses direkt beschreiben.
An jeder Position werden Steinpaare entfernt. Ein Paar an Position \(i\) wird zu einem Stein bei \(i+1\) und einem Stein bei \(i+3\). Der zurueckbleibende Digit an \(i\) ist daher nur \(0\) oder \(1\). Das ist wie eine Stellenwertdarstellung mit einer ungewoehnlichen Uebertragsregel:
$$2\cdot\text{Position }i \quad\longrightarrow\quad \text{Position }(i+1)+\text{Position }(i+3).$$
Wenn \(s_i\in\{0,1\}\) angibt, ob an Position \(i\) ein Singleton zurueckblieb, dann normalisiert der Prozess den Startwert \(n\) deterministisch zu einer Digitfolge \(s_0,s_1,s_2,\dots\). Die Sad-Bedingung ist anschliessend nur noch eine Bedingung an den Traeger dieser Folge.
Gib Position \(i\) das formale Gewicht \(x^i\). Damit die Uebertragsregel den Wert erhaelt, muss ein Paar an Position \(i\) denselben Wert haben wie die beiden weitergetragenen Steine:
$$2x^i=x^{i+1}+x^{i+3}.$$
Nach Division durch \(x^i\) ergibt sich
$$x^3+x-2=0.$$
Die Faktorisierung lautet
$$x^3+x-2=(x-1)(x^2+x+2).$$
Der Faktor \(x-1\) misst nur die Gesamtmasse. Das reicht hier nicht, weil die Masse unendlich weiterwandern kann. Die endliche Singleton-Spur wird vom quadratischen Faktor erfasst; daher arbeitet der Code in dem Ring mit
$$x^2+x+2=0,\qquad\text{also}\qquad x^2=-x-2.$$
Modulo \(x^2+x+2\) hat jede Potenz die Form
$$x^i=a_i+b_i x.$$
Die ersten beiden Werte sind \(x^0=1\) und \(x^1=x\). Falls \(x^{i-1}=a+b x\), dann gilt
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
Der Code speichert also nur zwei ganze Zahlen pro Position und benutzt den Uebergang
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
Fuer eine endliche Singleton-Menge \(P\) definieren wir
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
Ist \(P\) die vollstaendige endliche Singleton-Menge eines Startwertes \(n\), dann muss dieser Wert im quadratischen Quotienten gleich dem Anfangswert \(n\) sein. Ein gewoehnlicher Integer besitzt keinen \(x\)-Anteil, also lautet der Test
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
Der Links-nach-rechts-Prozess ist deterministisch: Ist \(n\) gegeben, dann sind der Paritaetsdigit \(s_i\) und der ausgehende Uebertrag an jeder Position festgelegt. Umgekehrt beschreibt eine endliche Digitmenge \(P\), deren quadratischer Wert ein positiver Integer ist, eine gueltige endliche Spur dieses Uebertragssystems. Der Code benutzt diese Entsprechung zwischen sad-Startwerten in \(S(k)\) und endlichen Mengen \(P\subseteq\{0,\dots,k-1\}\), die den algebraischen Test und die Abstandsbedingung erfuellen.
Deshalb wird am Ende auch nicht die Anzahl solcher Mengen addiert. Jede akzeptierte Menge \(P\) steht fuer den Startwert \(n=A(P)\), und \(S(k)\) verlangt die Summe dieser Startwerte.
Eine endliche Singleton-Menge \(P\) ist genau dann einsam, wenn
$$|i-j|\ge 3\qquad\text{fuer alle verschiedenen }i,j\in P.$$
Man kann dies als unabhaengige Menge in einem Pfadgraphen sehen, in dem Positionen in Abstand \(1\) oder \(2\) miteinander kollidieren. Die Aufgabe wird damit zu einer endlichen kombinatorischen Suche: Teilmengen mit Abstand \(3\) auflisten, ihren Wert zu \(A+Bx\) reduzieren, und nur positive Integer mit \(B=0\) behalten.
Die Beispiele passen direkt. \(\{0\}\) liefert \(1\). Die Menge \(\{2,5,8,13\}\) liefert \(68\), und \(\{1,13\}\) liefert \(90\). Dies sind die sad-Beitraege unterhalb von \(k=14\), also \(S(14)=1+68+90=159\).
Sei \(F(t)\) die Anzahl der Teilmengen von \(\{0,\dots,t-1\}\), deren Punkte paarweise mindestens Abstand \(3\) haben. Betrachtet man die letzte Position, erhaelt man
$$F(t)=F(t-1)+F(t-3).$$
Der Term \(F(t-1)\) zaehlt Teilmengen ohne die letzte Position; der Term \(F(t-3)\) zaehlt Teilmengen mit der letzten Position, weil dann die beiden vorherigen Positionen verboten sind. Fuer \(t=80\) ergibt das bereits \(25058735850088\) Kandidaten, also viel zu viele.
Der Schnitt bei \(m=\lfloor k/2\rfloor\) aendert die Groessenordnung. Fuer \(k=80\) hat jede Haelfte Laenge \(40\), und die Anzahl gueltiger Halb-Teilmengen ist nur \(F(40)=5736961\). Millionen Zustaende sind handhabbar, Billionen nicht.
Schreibe den linken Wert als \(A_L+B_Lx\) und den rechten Wert als \(A_R+B_Rx\). Die Vereinigung repraesentiert genau dann einen positiven Integer, wenn
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
Die rechte Haelfte muss also nach dem Koeffizienten \(B_R\) durchsuchbar sein. Fuer eine linke Teilmenge wird der rechte Koeffizient \(-B_L\) gesucht, und jede kompatible rechte Teilmenge mit diesem Koeffizienten traegt den Startwert \(A_L+A_R\) bei.
Die C++-Implementierung speichert rechte Eintraege sortiert nach Koeffizient und haelt Praefixsummen der Konstanten. Damit funktioniert auch der allgemeine Fall mehrerer rechter Teilmengen mit gleichem Koeffizienten: binaere Suche findet den passenden Block, und eine zweite Suche entfernt Eintraege mit nichtpositiver Gesamtkonstante. Die Python- und Java-Portierungen benutzen eine leichtere Tabelle von Koeffizient zu Konstante, weil die rechten Koeffizienten fuer \(k\le80\) innerhalb jeder Randklasse eindeutig sind.
Nach dem Halbieren fehlt nur noch die Abstandsregel ueber die Schnittstelle. Eine linke Auswahl nahe \(m\) kann mit einer rechten Auswahl nahe \(m\) kollidieren. Der Code speichert genau die dafuer noetige Information.
Fuer die linke Haelfte ist die Kategorie
$$0:\text{ kein ausgewaehlter Punkt bei }m-2\text{ oder }m-1,\qquad 1:\text{ letzter}=m-2,\qquad 2:\text{ letzter}=m-1.$$
Fuer die rechte Haelfte ist die Kategorie
$$0:\text{ kein ausgewaehlter Punkt bei }m\text{ oder }m+1,\qquad 1:\text{ erster}=m+1,\qquad 2:\text{ erster}=m.$$
Linkskategorie \(0\) verursacht keinen Randkonflikt. Bei Kategorie \(1\) ist nur Rechtskategorie \(2\) zu nah. Bei Kategorie \(2\) sind sowohl \(m\) als auch \(m+1\) zu nah, also ist nur Rechtskategorie \(0\) erlaubt. Diese Kompatibilitaetsregel ist exakt die Bedingung \(|i-j|\ge3\) ueber die Grenze hinweg.
build_powers konstruiert die Paare \((a_i,b_i)\) fuer \(x^i=a_i+b_i x\). evaluate_positions summiert diese Paare fuer eine vorgeschlagene Singleton-Menge. singleton_positions simuliert den Steinprozess fuer kleine Kontrollen direkt und bestaetigt damit sowohl die Algebra als auch die Interpretation der Singleton-Spur.
enumerate_right listet rekursiv alle gueltigen rechten Halb-Teilmengen auf und legt sie in den drei Randklassen ab. Jeder Eintrag enthaelt den reduzierten Koeffizienten und die Konstante. build_left_tasks erzeugt kurze linke Praefixe; die C++-Version verteilt damit die tiefere linke Suche auf mehrere Threads.
combine_left_dfs vervollstaendigt jede linke Teilmenge, berechnet ihre Randkategorie und fragt nur kompatible rechte Klassen ab. Ein Treffer wird akzeptiert, wenn die Koeffizienten sich aufheben und die Konstantensumme positiv ist. Genau diese positive Konstante wird addiert, denn sie ist der repraesentierte Startwert.
Die Pruefungen bestaetigen die bekannten Spuren fuer \(n=1\), \(n=68\) und \(n=90\), danach \(S(14)=159\) und \(S(30)=33438\). Erst anschliessend wird \(S(80)\) berechnet.
Die ungeteilte Suche wuerde \(F(k)\) abstandsgueltige Teilmengen untersuchen und ist fuer \(k=80\) nicht praktikabel. Die Meet-in-the-middle-Methode speichert \(O(F(k/2))\) rechte Zustaende und fuehrt \(O(F(k/2))\) linke Suchen aus.
In der sortierten C++-Variante kostet der Aufbau der rechten Tabellen \(O(F(k/2)\log F(k/2))\), und jede abgeschlossene linke Teilmenge fuehrt nur konstant viele binaere Suchen aus. Die Hash-Tabellen in Python und Java haben fuer den tatsaechlichen Bereich \(k\le80\) erwartete \(O(F(k/2))\) Aufbauzeit und erwartete konstante Nachschlagezeit. Der Speicherbedarf ist \(O(F(k/2))\).
Süreç \(0\) konumunda \(n\) taşla başlar. Sonra konumlar artan sırayla işlenir. Geçerli \(i\) konumunda \(m\) taş varsa, \(m\) tek olduğunda burada tam bir singleton bırakılır; her durumda \(\lfloor m/2\rfloor\) taş \(i+1\)'e, bir \(\lfloor m/2\rfloor\) taş da \(i+3\)'e gönderilir.
Bu problem için önemli olan şey, hangi konumlarda geçerli taş yığınının tek olduğudur. Bir singleton, uzaklığı \(1\) veya \(2\) olan başka bir singleton yoksa lonely sayılır. Dolayısıyla sad bir başlangıç değeri, singleton konumları arasında çiftler halinde en az \(3\) mesafe olan bir başlangıç değeridir. \(S(k)\), tam singleton kümesi \(0\le i\lt k\) içinde kalan tüm sad başlangıç değerlerini toplar. Hedef \(S(80)\)'dir; problem \(S(14)=159\) ve \(S(30)=33438\) kontrollerini verir.
Asıl zorluk, sürecin birçok başlangıç değerinde bitmemesidir. Taşlar sonsuza kadar sağa taşınmaya devam ederken geride yalnızca sonlu sayıda singleton bırakabilir. Bu yüzden çözüm, tüm taşların yok olmasını bekleyen bir simülasyona dayanamaz; sürecin bıraktığı sonlu parite izini karakterize etmelidir.
Her konumda taş çiftleri kaldırılır ve \(i\) konumundaki her çift, \(i+1\)'de bir taş ve \(i+3\)'te bir taş hâline gelir. \(i\)'de kalabilecek basamak yalnızca \(0\) ya da \(1\)'dir. Bu, alışılmış basamaklı sayı sistemlerindeki elde işlemine benzer; tek fark taşıma kuralının şu olmasıdır:
$$2e_i\quad\longrightarrow\quad e_{i+1}+e_{i+3}.$$
\(s_i\in\{0,1\}\), \(i\)'de singleton bırakılıp bırakılmadığını göstersin. O zaman süreç, başlangıç yığını \(n\)'yi deterministik biçimde \(s_0,s_1,s_2,\dots\) basamak dizisine normalleştirir. Sad olma koşulu, bu dizinin destek kümesi üzerinde bir koşula dönüşür.
\(i\) konumuna \(x^i\) biçimsel ağırlığını verelim. Taşıma kuralının ağırlığı koruması için, \(i\)'deki bir çift taşın değeri, taşınan iki taşın toplam değerine eşit olmalıdır:
$$2x^i=x^{i+1}+x^{i+3}.$$
\(x^i\)'ye bölersek
$$x^3+x-2=0$$
elde ederiz. Bu polinom
$$x^3+x-2=(x-1)(x^2+x+2)$$
diye çarpanlara ayrılır. \(x-1\) çarpanı yalnızca toplam taş miktarını izler; süreç sonsuza kadar sürebildiği için bu tek başına yeterli değildir. Sonlu singleton izi, ikinci dereceden çarpanla yakalanır. Bu yüzden uygulama
$$x^2+x+2=0,\qquad x^2=-x-2$$
ilişkisi içinde çalışır.
\(x^2+x+2\)'ye göre her kuvvet
$$x^i=a_i+b_i x$$
biçimine indirgenir. İlk iki değer \(x^0=1\) ve \(x^1=x\)'tir. Eğer \(x^{i-1}=a+b x\) ise
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
Dolayısıyla kod her konum için yalnızca iki tamsayı tutar ve şu geçişi kullanır:
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
Sonlu bir singleton kümesi \(P\) için
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x$$
tanımını yapalım. Eğer \(P\), bir başlangıç değeri \(n\)'nin tam sonlu singleton kümesiyse, bu değer ikinci dereceden bölüm halkasında başlangıç değeri \(n\)'ye eşit olmalıdır. Sıradan bir tamsayının \(x\)-bileşeni olmadığı için gerekli test
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0$$
şeklindedir.
Soldan sağa süreç deterministiktir: \(n\) sabitlenince \(i\) konumundaki parite basamağı \(s_i\) ve oradan çıkan taşıma da sabitlenir. Ters yönden bakıldığında, ikinci dereceden değeri pozitif bir tamsayı olan sonlu bir basamak kümesi \(P\), bu taşıma sistemi altında o tamsayının geçerli sonlu izidir. Kod, \(S(k)\)'de sayılan sad başlangıç değerleriyle, cebirsel testi ve uzaklık koşulunu sağlayan sonlu \(P\subseteq\{0,\dots,k-1\}\) kümeleri arasındaki bu bire bir karşılığı kullanır.
Bu yüzden sonuç bir küme sayısı değildir. Kabul edilen her \(P\) kümesi \(n=A(P)\) başlangıç değerini temsil eder ve \(S(k)\) bu başlangıç değerlerinin toplamını ister.
Sonlu bir singleton kümesi \(P\), ancak ve ancak
$$|i-j|\ge 3\qquad(i\ne j,\; i,j\in P)$$
koşulunu sağlıyorsa lonely olur. Bunu, \(0,1,\dots,k-1\) konumlarından oluşan ve uzaklığı \(1\) veya \(2\) olan konumları çatışmalı sayan bir yol grafında bağımsız küme olarak da görebiliriz. Problem artık sonlu bir kombinatorik listelemedir: aralığı en az \(3\) olan alt kümeleri üret, değerlerini \(A+Bx\)'e indir, yalnızca \(B=0\) ve \(A\gt0\) olanları sakla.
Örnekler doğrudan çıkar. \(\{0\}\) kümesi \(1\)'i verir. \(\{2,5,8,13\}\) kümesi \(68\)'i, \(\{1,13\}\) kümesi \(90\)'ı verir. Bunlar \(k=14\) altındaki sad katkılardır; dolayısıyla \(S(14)=1+68+90=159\).
\(\{0,\dots,t-1\}\) içinde seçilen her iki konum arasında en az \(3\) mesafe olan alt kümelerin sayısı \(F(t)\) olsun. Son konuma bakarsak
$$F(t)=F(t-1)+F(t-3)$$
elde ederiz. \(F(t-1)\), son konumu kullanmayan alt kümeleri sayar. \(F(t-3)\), son konumu kullananları sayar; çünkü bu durumda önceki iki konum yasaktır. \(t=80\) için bu sayı \(25058735850088\)'e çıkar. Bu doğrudan arama için çok büyüktür.
Kesimi \(m=\lfloor k/2\rfloor\) noktasında yapmak ölçeği değiştirir. \(k=80\) için her yarı uzunluğu \(40\)'tır ve geçerli yarı-alt-küme sayısı yalnızca \(F(40)=5736961\)'dir. Milyonlarca durum yönetilebilir; onlarca trilyon durum yönetilemez.
Sol yarının değerini \(A_L+B_Lx\), sağ yarının değerini \(A_R+B_Rx\) olarak yazalım. Birleşim tam olarak şu durumda pozitif bir tamsayı temsil eder:
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
Bu yüzden sağ yarının \(B_R\) katsayısına göre aranabilir olması yeterlidir. Her sol alt küme için gereken sağ katsayı \(-B_L\)'dir; bu katsayıya sahip her uyumlu sağ alt küme \(A_L+A_R\) başlangıç değerini katkı olarak ekler.
C++ uygulaması sağ girdileri katsayıya göre sıralar ve sabitlerin prefix toplamlarını tutar. Böylece aynı katsayıya sahip birden fazla sağ alt küme olsa bile genel durum desteklenir: ikili arama uygun bloğu bulur, ikinci arama ise toplam sabiti pozitif olmayanları eler. Python ve Java portları, \(k\le80\) aralığında sağ katsayılar her sınır sınıfı içinde tekil olduğu için daha hafif bir katsayıdan sabite tablo kullanır.
Yarıya bölmeden sonra eksik kalan tek koşul, kesim noktasını geçen uzaklık kuralıdır. \(m\)'ye yakın seçilmiş bir sol konum, \(m\)'ye yakın seçilmiş bir sağ konumla çakışabilir. Kod bu karar için gereken en küçük bilgiyi saklar.
Sol yarı için kategori şöyledir:
Sol kategoriler \(L=0,1,2\) olarak tutulur: \(L=0\) için \(m-2\) ve \(m-1\) seçili değildir, \(L=1\) için son seçim \(m-2\)'dir, \(L=2\) için son seçim \(m-1\)'dir.
Sağ yarı için kategori şöyledir:
Sağ kategoriler \(R=0,1,2\) olarak tutulur: \(R=0\) için \(m\) ve \(m+1\) seçili değildir, \(R=1\) için ilk seçim \(m+1\)'dir, \(R=2\) için ilk seçim \(m\)'dir.
Sol kategori \(0\) ise sınır çatışması yoktur. Sol kategori \(1\) ise yalnızca sağ kategori \(2\) fazla yakındır. Sol kategori \(2\) ise hem \(m\) hem \(m+1\) fazla yakındır; bu yüzden yalnızca sağ kategori \(0\) kabul edilir. Bu üçe üç uyumluluk kuralı, kesimden geçen \(|i-j|\ge3\) koşulunun tam karşılığıdır.
build_powers, \(x^i=a_i+b_i x\) temsilindeki \((a_i,b_i)\) çiftlerini üretir. evaluate_positions önerilen bir singleton kümesi için bu çiftleri toplar. singleton_positions küçük kontrollerde taş sürecini doğrudan simüle eder; böylece hem cebirsel temsil hem de singleton izinin yorumu doğrulanır.
enumerate_right, sağ yarıdaki tüm geçerli aralığı-\(3\) alt kümeleri rekürsif olarak üretir ve onları üç sınır kovasına koyar. Her kayıt indirgenmiş katsayıyı ve sabiti içerir. build_left_tasks sığ sol önekler oluşturur; C++ sürümü daha derin sol aramayı iş parçacıklarına bölmek için bunları kullanır.
combine_left_dfs her sol alt kümeyi tamamlar, sınır kategorisini hesaplar ve yalnızca uyumlu sağ kovaları sorgular. Katsayılar birbirini götürüyorsa ve sabit toplamı pozitifse eşleşme kabul edilir. Eklenen değer bu pozitif sabittir; çünkü temsil edilen başlangıç değeri odur.
Kontrol takımı \(n=1\), \(n=68\), \(n=90\) için bilinen izleri doğrular; ardından \(S(14)=159\) ve \(S(30)=33438\) kontrollerini çalıştırır. Program \(S(80)\)'i ancak bu kontrollerden sonra hesaplar.
Bölünmemiş arama \(F(k)\) geçerli alt kümeyi incelemek zorunda kalır ve \(k=80\) için uygulanabilir değildir. Meet-in-the-middle yöntemi \(O(F(k/2))\) sağ-yarı durumu saklar ve \(O(F(k/2))\) sol-yarı araması yapar.
Sıralı tablo kullanan C++ sürümünde sağ tabloları kurmak \(O(F(k/2)\log F(k/2))\) sürer; tamamlanan her sol alt küme sabit sayıda ikili arama yapar. Python ve Java'daki tablo tabanlı sürümlerde, gerçek \(k\le80\) aralığı için tablo kurulumu beklenen \(O(F(k/2))\), sorgular ise beklenen sabit zamandır. Bellek kullanımı \(O(F(k/2))\)'dir.
El proceso empieza con \(n\) piedras en la posición \(0\). Luego se procesan las posiciones en orden creciente. Si la posición actual \(i\) contiene \(m\) piedras, se deja un singleton exactamente cuando \(m\) es impar; en todos los casos se envían \(\lfloor m/2\rfloor\) piedras a \(i+1\) y otras \(\lfloor m/2\rfloor\) piedras a \(i+3\).
Para este problema solo importan las posiciones donde el montón actual era impar. Un singleton es solitario cuando no hay otro singleton a distancia \(1\) o \(2\). Por tanto, un entero triste es un valor inicial cuyas posiciones de singleton están separadas por al menos \(3\) de dos en dos. \(S(k)\) suma todos esos valores iniciales cuyo conjunto completo de singletons está contenido en \(0\le i\lt k\). Se pide \(S(80)\), y el enunciado da los controles \(S(14)=159\) y \(S(30)=33438\).
La dificultad principal es que muchos valores iniciales no terminan. Incluso si las piedras siguen moviéndose hacia la derecha indefinidamente, el proceso puede dejar solo un número finito de singletons. Así que no basta con simular hasta que desaparezcan todas las piedras; hay que caracterizar directamente la traza finita de paridades.
En cada posición se eliminan pares de piedras, y cada par en \(i\) se convierte en una piedra en \(i+1\) y una piedra en \(i+3\). El dígito que queda en \(i\) solo puede ser \(0\) o \(1\). Esto se parece a una normalización en un sistema posicional, salvo que la regla de acarreo es inusual:
$$2e_i\quad\longrightarrow\quad e_{i+1}+e_{i+3}.$$
Si \(s_i\in\{0,1\}\) registra si se dejó un singleton en \(i\), entonces el proceso normaliza determinísticamente el montón inicial \(n\) en una secuencia de dígitos \(s_0,s_1,s_2,\dots\). La condición de tristeza se convierte en una condición sobre el soporte de esa secuencia.
Asignemos el peso formal \(x^i\) a la posición \(i\). Para que la regla de acarreo conserve el valor, un par en la posición \(i\) debe valer lo mismo que las dos piedras transportadas:
$$2x^i=x^{i+1}+x^{i+3}.$$
Al dividir por \(x^i\), se obtiene
$$x^3+x-2=0.$$
El polinomio factoriza como
$$x^3+x-2=(x-1)(x^2+x+2).$$
El factor \(x-1\) solo sigue la masa total, lo cual no basta porque el proceso puede continuar para siempre. La traza finita de singletons queda capturada por el factor cuadrático; por eso la implementación trabaja en el anillo donde
$$x^2+x+2=0,\qquad\text{equivalentemente}\qquad x^2=-x-2.$$
Módulo \(x^2+x+2\), toda potencia tiene la forma
$$x^i=a_i+b_i x.$$
Los dos primeros valores son \(x^0=1\) y \(x^1=x\). Si \(x^{i-1}=a+b x\), entonces
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
Así el código guarda solo dos enteros por posición y avanza con
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
Para un conjunto finito de singletons \(P\), definimos
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
Si \(P\) es el conjunto completo de singletons de algún valor inicial \(n\), entonces su valor en este cociente cuadrático debe ser el entero inicial \(n\), que no tiene parte en \(x\). Por tanto, el test algebraico es
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
El proceso de izquierda a derecha es determinista: una vez fijado \(n\), quedan fijados el dígito de paridad \(s_i\) y el acarreo saliente de cada posición. En sentido inverso, un conjunto finito de dígitos \(P\) cuyo valor cuadrático es un entero positivo es una traza finita válida para ese entero bajo esta regla de acarreo. El programa usa esta biyección entre los valores iniciales tristes contados por \(S(k)\) y los conjuntos finitos \(P\subseteq\{0,\dots,k-1\}\) que satisfacen el test algebraico y la separación de soledad.
Esto explica también por qué el resultado final no es un conteo. Cada conjunto aceptado \(P\) representa un valor inicial \(n=A(P)\), y \(S(k)\) pide la suma de esos valores iniciales.
Un conjunto finito \(P\) de posiciones de singleton es solitario exactamente cuando
$$|i-j|\ge 3\qquad(i\ne j,\; i,j\in P).$$
Equivale a un conjunto independiente en el camino de posiciones \(0,1,\dots,k-1\), si se consideran incompatibles las posiciones a distancia \(1\) o \(2\). La tarea pasa a ser una enumeración combinatoria finita: listar subconjuntos con separación \(3\), reducir su valor a \(A+Bx\), y conservar solo los enteros positivos con \(B=0\).
Los ejemplos salen de inmediato. \(\{0\}\) da \(1\). El conjunto \(\{2,5,8,13\}\) da \(68\), y \(\{1,13\}\) da \(90\). Esas son las contribuciones tristes por debajo de \(k=14\), así que \(S(14)=1+68+90=159\).
Sea \(F(t)\) el número de subconjuntos de \(\{0,\dots,t-1\}\) con distancia mutua al menos \(3\). Al mirar la última posición se obtiene
$$F(t)=F(t-1)+F(t-3).$$
El término \(F(t-1)\) cubre los subconjuntos que no usan la última posición; el término \(F(t-3)\) cubre los que sí la usan, porque entonces las dos posiciones anteriores quedan prohibidas. Para \(t=80\), esto da \(25058735850088\) candidatos, demasiado para enumerarlos directamente.
Dividir en \(m=\lfloor k/2\rfloor\) cambia la escala. Para \(k=80\), cada mitad tiene longitud \(40\), y el número de subconjuntos válidos de media longitud es solo \(F(40)=5736961\). Millones de estados son manejables; decenas de billones no lo son.
Escribamos el valor de la mitad izquierda como \(A_L+B_Lx\) y el de la mitad derecha como \(A_R+B_Rx\). La unión representa un entero positivo exactamente cuando
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
Así, basta con que la mitad derecha se pueda buscar por su coeficiente \(B_R\). Para cada subconjunto izquierdo, el coeficiente derecho requerido es \(-B_L\), y cada subconjunto derecho compatible con ese coeficiente contribuye el valor inicial \(A_L+A_R\).
La implementación C++ almacena las entradas derechas ordenadas por coeficiente y mantiene sumas prefijas de constantes. Eso permite cubrir incluso el caso general en que muchas entradas derechas tengan el mismo coeficiente: una búsqueda binaria localiza el bloque, y otra descarta las entradas cuya constante total no es positiva. Las versiones Python y Java usan una tabla más ligera de coeficiente a constante porque, para las instancias \(k\le80\), los coeficientes derechos son únicos dentro de cada clase de frontera.
Después de partir el intervalo, solo falta la regla de distancia a través del corte. Un subconjunto izquierdo que termina cerca de \(m\) puede entrar en conflicto con un subconjunto derecho que empieza cerca de \(m\). El código guarda exactamente la información necesaria.
Para la mitad izquierda, la categoría es
Las categorías izquierdas son \(L=0,1,2\): \(L=0\) significa que no se eligió ni \(m-2\) ni \(m-1\), \(L=1\) significa que la última elección es \(m-2\), y \(L=2\) significa que la última elección es \(m-1\).
Para la mitad derecha, la categoría es
Las categorías derechas son \(R=0,1,2\): \(R=0\) significa que no se eligió ni \(m\) ni \(m+1\), \(R=1\) significa que la primera elección es \(m+1\), y \(R=2\) significa que la primera elección es \(m\).
Si la categoría izquierda es \(0\), no hay conflicto de frontera. Si es \(1\), solo la categoría derecha \(2\) está demasiado cerca. Si es \(2\), tanto \(m\) como \(m+1\) están demasiado cerca, de modo que solo se permite la categoría derecha \(0\). Esta regla de compatibilidad es exactamente la forma transfronteriza de \(|i-j|\ge3\).
build_powers construye los pares \((a_i,b_i)\) para \(x^i=a_i+b_i x\). evaluate_positions suma esos pares para un conjunto propuesto de singletons. singleton_positions simula directamente el proceso de piedras en casos pequeños, lo que verifica tanto la representación algebraica como la interpretación de la traza de singletons.
enumerate_right enumera recursivamente todos los subconjuntos válidos de la mitad derecha y los coloca en las tres cubetas de frontera. Cada entrada guarda el coeficiente reducido y la constante. build_left_tasks crea prefijos izquierdos poco profundos; la versión C++ los usa para repartir la búsqueda izquierda más profunda entre varios hilos.
combine_left_dfs completa cada subconjunto izquierdo, calcula su categoría de frontera y consulta solo cubetas derechas compatibles. Una coincidencia se acepta cuando los coeficientes se cancelan y la suma de constantes es positiva. Esa constante positiva se añade a la respuesta porque es el valor inicial representado.
La batería de comprobaciones verifica las trazas conocidas para \(n=1\), \(n=68\) y \(n=90\), y luego \(S(14)=159\) y \(S(30)=33438\). Solo después se evalúa \(S(80)\).
La búsqueda sin dividir examinaría \(F(k)\) subconjuntos válidos por separación, lo que no es factible para \(k=80\). El método meet-in-the-middle almacena \(O(F(k/2))\) estados derechos y realiza \(O(F(k/2))\) búsquedas izquierdas.
En la versión C++ con tablas ordenadas, construir las tablas derechas cuesta \(O(F(k/2)\log F(k/2))\), y cada subconjunto izquierdo completo hace solo un número constante de búsquedas binarias. Las versiones Python y Java basadas en tablas hash tienen construcción esperada \(O(F(k/2))\) y consultas esperadas de tiempo constante para el rango real \(k\le80\). El uso de memoria es \(O(F(k/2))\).
过程从位置 \(0\) 的 \(n\) 个石子开始。随后按递增顺序处理各个位置。若当前位置 \(i\) 有 \(m\) 个石子，则当且仅当 \(m\) 为奇数时在此留下一个单石；无论奇偶，都把 \(\lfloor m/2\rfloor\) 个石子移到 \(i+1\)，并把另外 \(\lfloor m/2\rfloor\) 个石子移到 \(i+3\)。
本题只关心当前石堆为奇数的位置。一个单石若与任何其他单石的距离都不是 \(1\) 或 \(2\)，就称为 lonely。因此 sad 初始值的单石位置必须两两相距至少 \(3\)。\(S(k)\) 要求把所有完整单石集合包含在 \(0\le i\lt k\) 中的 sad 初始值相加。目标是 \(S(80)\)，题目给出 \(S(14)=159\) 和 \(S(30)=33438\) 作为校验。
主要困难在于，许多初始值对应的过程不会终止。即使石子永远向右传播，留下的单石位置仍可能只有有限多个。因此解法不能依赖“模拟到没有石子为止”；它必须直接刻画过程留下的有限奇偶轨迹。
在每个位置，石子成对被移走；位置 \(i\) 的一对石子会变成位置 \(i+1\) 的一个石子和位置 \(i+3\) 的一个石子。因此留在 \(i\) 的“数字”只能是 \(0\) 或 \(1\)。这类似于一个位值系统中的进位，只是进位规则比较特殊：
$$2e_i\quad\longrightarrow\quad e_{i+1}+e_{i+3}.$$
令 \(s_i\in\{0,1\}\) 表示位置 \(i\) 是否留下单石。于是该过程把初始石堆 \(n\) 确定性地规范化为数字序列 \(s_0,s_1,s_2,\dots\)。sad 条件随后变成这个序列支撑集上的条件。
给位置 \(i\) 赋形式权重 \(x^i\)。为了让进位规则保持数值，位置 \(i\) 的一对石子必须与两个被移动后的石子具有相同权重：
$$2x^i=x^{i+1}+x^{i+3}.$$
除以 \(x^i\)，得到
$$x^3+x-2=0.$$
这个多项式分解为
$$x^3+x-2=(x-1)(x^2+x+2).$$
因子 \(x-1\) 只记录总质量；由于过程可能永远继续，这并不足以描述有限的单石轨迹。真正有用的是二次因子，所以实现工作在满足
$$x^2+x+2=0,\qquad x^2=-x-2$$
的环中。
模 \(x^2+x+2\) 后，每个幂都可写成
$$x^i=a_i+b_i x.$$
前两个值是 \(x^0=1\) 和 \(x^1=x\)。如果 \(x^{i-1}=a+b x\)，则
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
因此代码对每个位置只存两个整数，并用
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}$$
推进。对一个有限单石集合 \(P\)，定义
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
如果 \(P\) 是某个初始值 \(n\) 的完整有限单石集合，那么它在这个二次商环中的值必须等于初始整数 \(n\)，而普通整数没有 \(x\) 部分。因此代数测试是
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
从左到右的过程是确定性的：一旦 \(n\) 固定，每个位置的奇偶数字 \(s_i\) 和从该位置发出的进位都固定。反过来，一个有限数字集合 \(P\) 若在二次商中表示正整数，就给出了该整数在这个进位规则下的一条有效有限轨迹。程序正是利用这个对应关系，把 \(S(k)\) 中的 sad 初始值转化为满足代数测试和距离条件的有限集合 \(P\subseteq\{0,\dots,k-1\}\)。
这也说明为什么最后加的不是集合个数。每个被接受的集合 \(P\) 表示一个初始值 \(n=A(P)\)，而 \(S(k)\) 要求这些初始值的总和。
有限单石集合 \(P\) 孤独，当且仅当
$$|i-j|\ge 3\qquad(i\ne j,\; i,j\in P).$$
也可以把 \(0,1,\dots,k-1\) 看成路径图，并把距离 \(1\) 或 \(2\) 的点视为冲突点；此时 \(P\) 就是独立集。问题于是变成有限组合枚举：列出间距至少为 \(3\) 的子集，把其值化为 \(A+Bx\)，只保留 \(B=0\) 且 \(A\gt0\) 的正整数。
例子可直接验证。集合 \(\{0\}\) 给出 \(1\)。集合 \(\{2,5,8,13\}\) 给出 \(68\)，集合 \(\{1,13\}\) 给出 \(90\)。它们是 \(k=14\) 以下的 sad 贡献，所以 \(S(14)=1+68+90=159\)。
设 \(F(t)\) 是 \(\{0,\dots,t-1\}\) 中任意两点距离至少为 \(3\) 的子集数。观察最后一个位置可得
$$F(t)=F(t-1)+F(t-3).$$
\(F(t-1)\) 对应不选最后位置的子集；\(F(t-3)\) 对应选最后位置的子集，因为此时前两个位置被禁止。对 \(t=80\)，候选数已经达到 \(25058735850088\)，无法直接枚举。
在 \(m=\lfloor k/2\rfloor\) 处切开会显著降低规模。对 \(k=80\)，每一半长度为 \(40\)，有效半子集数只有 \(F(40)=5736961\)。数百万个状态可以处理，数十万亿个状态不能。
把左半的值写作 \(A_L+B_Lx\)，右半的值写作 \(A_R+B_Rx\)。合并后表示正整数当且仅当
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
因此右半只需要能按系数 \(B_R\) 查询。对每个左子集，需要的右系数是 \(-B_L\)，所有具有该系数且边界兼容的右子集都会贡献初始值 \(A_L+A_R\)。
C++ 实现把右侧条目按系数排序，并保存常数的前缀和。这样即使一般情况下多个右子集具有同一系数，也能用二分查找定位匹配区间，再用第二次二分排除总常数非正的条目。Python 和 Java 版本利用实际 \(k\le80\) 范围内每个边界类的右系数唯一这一事实，使用更轻量的“系数到常数”表。
切分之后唯一剩下的问题是跨边界的距离规则。左边靠近 \(m\) 的选择可能与右边靠近 \(m\) 的选择冲突。代码只记录判断这一点所需的信息。
对左半，类别为
左半类别记为 \(L=0,1,2\)：\(L=0\) 表示 \(m-2\) 和 \(m-1\) 都未被选中，\(L=1\) 表示最后选择的是 \(m-2\)，\(L=2\) 表示最后选择的是 \(m-1\)。
对右半，类别为
右半类别记为 \(R=0,1,2\)：\(R=0\) 表示 \(m\) 和 \(m+1\) 都未被选中，\(R=1\) 表示第一个选择的是 \(m+1\)，\(R=2\) 表示第一个选择的是 \(m\)。
左类别 \(0\) 没有边界冲突。左类别 \(1\) 只与右类别 \(2\) 过近。左类别 \(2\) 与 \(m\) 和 \(m+1\) 都过近，所以只允许右类别 \(0\)。这个兼容规则正是跨边界的 \(|i-j|\ge3\) 条件。
build_powers 构造表示 \(x^i=a_i+b_i x\) 的 \((a_i,b_i)\) 对。evaluate_positions 对给定单石集合求这些对的和。singleton_positions 在小样例中直接模拟石子过程，从而同时验证代数表示和单石轨迹的解释。
enumerate_right 递归枚举所有右半的间距合法子集，并放入三个边界桶中。每个条目保存化简后的系数和常数。build_left_tasks 生成较浅的左前缀；C++ 版本用它们把更深的左搜索分给多个线程。
combine_left_dfs 完成每个左子集，计算其边界类别，并只查询兼容的右桶。若系数相消且常数和为正，就接受这次匹配。加入答案的是这个正的常数，因为它就是所表示的初始值。
校验部分验证 \(n=1\)、\(n=68\)、\(n=90\) 的已知轨迹，然后验证 \(S(14)=159\) 和 \(S(30)=33438\)。只有这些检查通过后，程序才计算 \(S(80)\)。
不切分的搜索需要检查 \(F(k)\) 个间距合法子集，对 \(k=80\) 不可行。Meet-in-the-middle 方法保存 \(O(F(k/2))\) 个右半状态，并执行 \(O(F(k/2))\) 次左半搜索。
在排序表的 C++ 版本中，构建右表需要 \(O(F(k/2)\log F(k/2))\)，每个完整左子集只做常数次二分查询。Python 和 Java 的表结构在实际 \(k\le80\) 范围内有期望 \(O(F(k/2))\) 的构建时间和期望常数查询时间。内存使用为 \(O(F(k/2))\)。
Процесс начинается с \(n\) камней в позиции \(0\). Затем позиции обрабатываются в возрастающем порядке. Если в текущей позиции \(i\) находится \(m\) камней, то один одиночный камень остается там ровно тогда, когда \(m\) нечетно; в любом случае \(\lfloor m/2\rfloor\) камней отправляются в \(i+1\), и еще \(\lfloor m/2\rfloor\) камней отправляются в \(i+3\).
Для этой задачи важны только позиции, где текущая куча была нечетной. Одиночный камень считается lonely, если нет другого одиночного камня на расстоянии \(1\) или \(2\). Поэтому sad-начальное значение имеет одиночные позиции, попарно разделенные расстоянием хотя бы \(3\). \(S(k)\) суммирует все такие начальные значения, полный набор одиночных позиций которых содержится в \(0\le i\lt k\). Требуется \(S(80)\), а в условии даны проверки \(S(14)=159\) и \(S(30)=33438\).
Главная трудность в том, что для многих начальных значений процесс не завершается. Камни могут бесконечно уходить вправо, но при этом оставить только конечное число одиночных позиций. Поэтому решение не может ждать исчезновения всех камней; оно должно описать конечный след четности напрямую.
В каждой позиции пары камней удаляются, и каждая пара в позиции \(i\) превращается в один камень в \(i+1\) и один камень в \(i+3\). Остаточная цифра в позиции \(i\) поэтому равна только \(0\) или \(1\). Это похоже на перенос в позиционной системе счисления, но правило переноса необычно:
$$2e_i\quad\longrightarrow\quad e_{i+1}+e_{i+3}.$$
Если \(s_i\in\{0,1\}\) показывает, остался ли одиночный камень в \(i\), то процесс детерминированно нормализует начальную кучу \(n\) в последовательность цифр \(s_0,s_1,s_2,\dots\). Условие sad затем становится условием на носитель этой последовательности.
Назначим позиции \(i\) формальный вес \(x^i\). Чтобы правило переноса сохраняло значение, пара в позиции \(i\) должна иметь тот же вес, что и два перенесенных камня:
$$2x^i=x^{i+1}+x^{i+3}.$$
После деления на \(x^i\) получаем
$$x^3+x-2=0.$$
Многочлен раскладывается так:
$$x^3+x-2=(x-1)(x^2+x+2).$$
Фактор \(x-1\) отслеживает только полную массу, а этого недостаточно, потому что процесс может продолжаться бесконечно. Конечный след одиночных камней описывается квадратичным фактором, поэтому реализация работает в кольце, где
$$x^2+x+2=0,\qquad x^2=-x-2.$$
По модулю \(x^2+x+2\) любая степень имеет вид
$$x^i=a_i+b_i x.$$
Первые два значения: \(x^0=1\) и \(x^1=x\). Если \(x^{i-1}=a+b x\), то
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
Поэтому код хранит только два целых числа для каждой позиции и использует переход
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
Для конечного множества одиночных позиций \(P\) зададим
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
Если \(P\) является полным конечным множеством одиночных позиций для некоторого начального \(n\), то его значение в этом квадратичном факторе должно быть равно начальному целому \(n\), у которого нет \(x\)-части. Значит, алгебраический тест таков:
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
Процесс слева направо детерминирован: если \(n\) задано, то цифра четности \(s_i\) и исходящий перенос из каждой позиции фиксированы. Обратно, конечное множество цифр \(P\), чье квадратичное значение является положительным целым числом, задает допустимый конечный след для этого целого при данном правиле переноса. Программа использует это соответствие между sad-значениями в \(S(k)\) и конечными множествами \(P\subseteq\{0,\dots,k-1\}\), удовлетворяющими алгебраическому тесту и условию расстояния.
По этой причине итоговая величина не является числом множеств. Каждое принятое множество \(P\) представляет начальное значение \(n=A(P)\), а \(S(k)\) просит сумму этих начальных значений.
Конечное множество \(P\) одиночных позиций является lonely ровно тогда, когда
$$|i-j|\ge 3\qquad(i\ne j,\; i,j\in P).$$
Эквивалентно, в пути на позициях \(0,1,\dots,k-1\), где вершины на расстоянии \(1\) или \(2\) конфликтуют, \(P\) является независимым множеством. Задача превращается в конечное комбинаторное перечисление: перечислить подмножества с зазором \(3\), свести их значение к \(A+Bx\), и оставить только положительные целые с \(B=0\).
Примеры сразу согласуются с этим. \(\{0\}\) дает \(1\). Множество \(\{2,5,8,13\}\) дает \(68\), а \(\{1,13\}\) дает \(90\). Это sad-вклады ниже \(k=14\), поэтому \(S(14)=1+68+90=159\).
Пусть \(F(t)\) — число подмножеств \(\{0,\dots,t-1\}\), в которых любые две выбранные позиции имеют расстояние хотя бы \(3\). Рассмотрение последней позиции дает
$$F(t)=F(t-1)+F(t-3).$$
Слагаемое \(F(t-1)\) покрывает подмножества без последней позиции; слагаемое \(F(t-3)\) покрывает подмножества с последней позицией, потому что две предыдущие позиции тогда запрещены. Для \(t=80\) это уже \(25058735850088\) кандидатов, что слишком много для прямого перебора.
Разделение в точке \(m=\lfloor k/2\rfloor\) меняет масштаб. При \(k=80\) каждая половина имеет длину \(40\), и число допустимых полуподмножеств равно только \(F(40)=5736961\). Миллионы состояний управляемы; десятки триллионов — нет.
Запишем значение левой половины как \(A_L+B_Lx\), а правой как \(A_R+B_Rx\). Их объединение представляет положительное целое ровно тогда, когда
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
Следовательно, правая половина должна быть доступна для поиска по коэффициенту \(B_R\). Для каждого левого подмножества нужен правый коэффициент \(-B_L\), и каждое совместимое правое подмножество с этим коэффициентом вносит начальное значение \(A_L+A_R\).
C++-реализация хранит правые записи отсортированными по коэффициенту и поддерживает префиксные суммы констант. Это покрывает даже общий случай, когда несколько правых подмножеств имеют один коэффициент: бинарный поиск находит нужный блок, а второй поиск отбрасывает записи с неположительной полной константой. Python- и Java-версии используют более легкую таблицу коэффициент-к-константе, потому что для фактического диапазона \(k\le80\) правые коэффициенты уникальны внутри каждого пограничного класса.
После разделения остается только правило расстояния через границу. Левое подмножество, заканчивающееся рядом с \(m\), может конфликтовать с правым подмножеством, начинающимся рядом с \(m\). Код хранит ровно ту информацию, которая нужна для решения.
Для левой половины категория такова:
Левые категории обозначаются \(L=0,1,2\): \(L=0\) означает, что не выбраны ни \(m-2\), ни \(m-1\); \(L=1\) означает, что последняя выбранная позиция равна \(m-2\); \(L=2\) означает, что последняя выбранная позиция равна \(m-1\).
Для правой половины категория такова:
Правые категории обозначаются \(R=0,1,2\): \(R=0\) означает, что не выбраны ни \(m\), ни \(m+1\); \(R=1\) означает, что первая выбранная позиция равна \(m+1\); \(R=2\) означает, что первая выбранная позиция равна \(m\).
Если левая категория равна \(0\), пограничного конфликта нет. Если она равна \(1\), слишком близка только правая категория \(2\). Если она равна \(2\), слишком близки и \(m\), и \(m+1\), поэтому разрешена только правая категория \(0\). Это правило совместимости является точной формой условия \(|i-j|\ge3\) через разрез.
build_powers строит пары \((a_i,b_i)\) для \(x^i=a_i+b_i x\). evaluate_positions суммирует эти пары для предполагаемого множества одиночных позиций. singleton_positions напрямую моделирует процесс для малых проверок, подтверждая и алгебраическое представление, и смысл следа одиночных камней.
enumerate_right рекурсивно перечисляет все допустимые подмножества правой половины с зазором \(3\) и помещает их в три пограничные корзины. Каждая запись содержит сведенный коэффициент и константу. build_left_tasks создает неглубокие левые префиксы; C++-версия использует их, чтобы распределить более глубокий левый поиск по рабочим потокам.
combine_left_dfs завершает каждое левое подмножество, вычисляет его пограничную категорию и запрашивает только совместимые правые корзины. Совпадение принимается, если коэффициенты сокращаются и сумма констант положительна. Эта положительная константа добавляется к ответу, потому что она и есть представленное начальное значение.
Набор проверок подтверждает известные следы для \(n=1\), \(n=68\) и \(n=90\), затем \(S(14)=159\) и \(S(30)=33438\). Только после этого вычисляется \(S(80)\).
Неразделенный поиск должен был бы рассмотреть \(F(k)\) допустимых по расстоянию подмножеств, что невозможно для \(k=80\). Метод meet-in-the-middle хранит \(O(F(k/2))\) правых состояний и выполняет \(O(F(k/2))\) левых поисков.
В C++-версии с отсортированными таблицами построение правых таблиц стоит \(O(F(k/2)\log F(k/2))\), а каждое завершенное левое подмножество выполняет только константное число бинарных поисков. Табличные Python- и Java-версии для фактического диапазона \(k\le80\) имеют ожидаемое \(O(F(k/2))\) построение и ожидаемое константное время запросов. Память равна \(O(F(k/2))\).
تبدأ العملية بعدد \(n\) من الحجارة في الموضع \(0\). بعد ذلك تُعالَج المواضع بترتيب تصاعدي. إذا كان الموضع الحالي \(i\) يحتوي على \(m\) حجراً، فإن حجراً منفرداً يترك هناك بالضبط عندما يكون \(m\) فردياً؛ وفي كل الأحوال يُرسَل \(\lfloor m/2\rfloor\) حجراً إلى \(i+1\)، ويُرسَل \(\lfloor m/2\rfloor\) حجراً آخر إلى \(i+3\).
ما يهم في هذه المسألة هو المواضع التي كان فيها الكوم الحالي فردياً. الحجر المنفرد يكون lonely إذا لم يوجد حجر منفرد آخر على مسافة \(1\) أو \(2\). لذلك فإن عدد البداية sad هو عدد تكون مواضع أحجاره المنفردة متباعدة زوجياً بمسافة لا تقل عن \(3\). الدالة \(S(k)\) تجمع كل قيم البداية sad التي تقع مجموعة مواضعها المنفردة الكاملة داخل \(0\le i\lt k\). المطلوب هو \(S(80)\)، ومعطى للتحقق أن \(S(14)=159\) و\(S(30)=33438\).
الصعوبة الأساسية أن العملية لا تنتهي لكثير من قيم البداية. قد تستمر الحجارة في الانتقال إلى اليمين إلى ما لا نهاية، ومع ذلك تترك عدداً منتهياً فقط من المواضع المنفردة. لذلك لا يمكن للحل أن يعتمد على محاكاة تنتظر اختفاء كل الحجارة؛ بل يجب أن يصف أثر الفردية المنتهي مباشرة.
في كل موضع تُزال أزواج الحجارة، وكل زوج عند الموضع \(i\) يتحول إلى حجر عند \(i+1\) وحجر عند \(i+3\). لذلك فإن الرقم الباقي عند \(i\) لا يمكن إلا أن يكون \(0\) أو \(1\). هذا يشبه الحمل في نظام تمثيل عددي، لكن قاعدة الحمل هنا غير مألوفة:
$$2e_i\quad\longrightarrow\quad e_{i+1}+e_{i+3}.$$
إذا كان \(s_i\in\{0,1\}\) يسجل هل تُرك حجر منفرد عند \(i\)، فإن العملية تحوّل كومة البداية \(n\) بشكل حتمي إلى متتالية أرقام \(s_0,s_1,s_2,\dots\). شرط sad يصبح بعد ذلك شرطاً على مجموعة المواضع التي تظهر فيها هذه الأرقام.
نعطي الموضع \(i\) الوزن الشكلي \(x^i\). لكي تحفظ قاعدة الحمل القيمة، يجب أن تكون قيمة زوج في الموضع \(i\) مساوية لقيمة الحجرين المحمولين:
$$2x^i=x^{i+1}+x^{i+3}.$$
بعد القسمة على \(x^i\)، نحصل على
$$x^3+x-2=0.$$
ويتفكك كثير الحدود إلى
$$x^3+x-2=(x-1)(x^2+x+2).$$
العامل \(x-1\) يتتبع الكتلة الكلية فقط، وهذا لا يكفي هنا لأن العملية قد تستمر إلى ما لا نهاية. الأثر المنتهي للأحجار المنفردة يلتقطه العامل التربيعي، لذلك يعمل التنفيذ في الحلقة التي تحقق
$$x^2+x+2=0,\qquad x^2=-x-2.$$
بترديد \(x^2+x+2\)، كل قوة لها الشكل
$$x^i=a_i+b_i x.$$
القيمتان الأوليان هما \(x^0=1\) و\(x^1=x\). إذا كان \(x^{i-1}=a+b x\)، فإن
$$x^i=x(a+b x)=a x+b x^2=a x+b(-x-2)=-2b+(a-b)x.$$
لذلك يخزن الكود عددين صحيحين فقط لكل موضع، وينتقل بواسطة
$$a_i=-2b_{i-1},\qquad b_i=a_{i-1}-b_{i-1}.$$
لمجموعة منتهية من المواضع المنفردة \(P\)، نعرّف
$$V(P)=\sum_{i\in P}x^i=A(P)+B(P)x.$$
إذا كانت \(P\) هي المجموعة الكاملة المنتهية للأحجار المنفردة لقيمة بداية \(n\)، فيجب أن تساوي قيمتها في هذا الخارج التربيعي العدد الابتدائي \(n\)، الذي لا يملك جزءاً مضروباً في \(x\). لذلك يكون الاختبار الجبري هو
$$B(P)=0,\qquad n=A(P),\qquad A(P)\gt0.$$
العملية من اليسار إلى اليمين حتمية: عندما تثبت \(n\)، فإن رقم الفردية \(s_i\) والحمل الخارج من كل موضع يتحددان. وبالعكس، فإن مجموعة أرقام منتهية \(P\) قيمتها التربيعية عدد صحيح موجب تمثل أثراً منتهياً صالحاً لذلك العدد تحت قاعدة الحمل هذه. يستخدم البرنامج هذه المراسلة بين قيم البداية sad التي تدخل في \(S(k)\) والمجموعات المنتهية \(P\subseteq\{0,\dots,k-1\}\) التي تحقق الاختبار الجبري وشرط التباعد.
وهذا يفسر أيضاً لماذا لا يكون الناتج النهائي مجرد عدد للمجموعات. كل مجموعة مقبولة \(P\) تمثل قيمة بداية \(n=A(P)\)، و\(S(k)\) تطلب مجموع قيم البداية هذه.
مجموعة مواضع منفردة منتهية \(P\) تكون lonely بالضبط عندما
$$|i-j|\ge 3\qquad(i\ne j,\; i,j\in P).$$
يمكن أيضاً رؤيتها كمجموعة مستقلة في مسار المواضع \(0,1,\dots,k-1\)، حيث المواضع على مسافة \(1\) أو \(2\) تتعارض. هكذا تصبح المسألة تعداداً تركيبياً منتهياً: ندرج المجموعات الجزئية ذات الفجوة \(3\)، نختزل قيمتها إلى \(A+Bx\)، ونحتفظ فقط بالأعداد الصحيحة الموجبة ذات \(B=0\).
الأمثلة تظهر مباشرة. المجموعة \(\{0\}\) تعطي \(1\). المجموعة \(\{2,5,8,13\}\) تعطي \(68\)، والمجموعة \(\{1,13\}\) تعطي \(90\). هذه هي مساهمات sad قبل \(k=14\)، ولذلك \(S(14)=1+68+90=159\).
ليكن \(F(t)\) عدد المجموعات الجزئية من \(\{0,\dots,t-1\}\) التي تكون المسافة بين أي موضعين مختارين فيها على الأقل \(3\). بالنظر إلى الموضع الأخير نحصل على
$$F(t)=F(t-1)+F(t-3).$$
الحد \(F(t-1)\) يمثل المجموعات التي لا تستخدم الموضع الأخير، والحد \(F(t-3)\) يمثل المجموعات التي تستخدمه، لأن الموضعين السابقين يصبحان ممنوعين. عندما \(t=80\)، يصل هذا إلى \(25058735850088\) مرشحاً، وهو أكبر بكثير من التعداد المباشر.
التقسيم عند \(m=\lfloor k/2\rfloor\) يغير الحجم. عند \(k=80\)، طول كل نصف هو \(40\)، وعدد المجموعات الجزئية الصالحة في النصف هو فقط \(F(40)=5736961\). ملايين الحالات قابلة للإدارة؛ عشرات التريليونات ليست كذلك.
لنكتب قيمة النصف الأيسر على الصورة \(A_L+B_Lx\)، وقيمة النصف الأيمن على الصورة \(A_R+B_Rx\). الاتحاد يمثل عدداً صحيحاً موجباً بالضبط عندما
$$B_L+B_R=0,\qquad A_L+A_R\gt0.$$
إذن يكفي أن يكون النصف الأيمن قابلاً للبحث حسب المعامل \(B_R\). لكل مجموعة جزئية يسارية، المعامل الأيمن المطلوب هو \(-B_L\)، وكل مجموعة جزئية يمينية متوافقة بهذا المعامل تساهم بقيمة البداية \(A_L+A_R\).
تخزن نسخة C++ الإدخالات اليمنى مرتبة حسب المعامل، وتحتفظ بمجاميع بادئة للثوابت. هذا يدعم حتى الحالة العامة التي توجد فيها عدة مجموعات يمينية لها المعامل نفسه: بحث ثنائي يجد الكتلة المطابقة، وبحث ثنائي آخر يستبعد الإدخالات التي يكون مجموع ثوابتها غير موجب. أما نسختا Python وJava فتستخدمان جدولاً أخف من المعامل إلى الثابت، لأن المعاملات اليمنى فريدة داخل كل فئة حدودية في المجال الفعلي \(k\le80\).
بعد التقسيم يبقى شرط المسافة عبر الحد. اختيار يساري قريب من \(m\) قد يتعارض مع اختيار يميني قريب من \(m\). يخزن الكود بالضبط المعلومات اللازمة لهذا القرار.
بالنسبة إلى النصف الأيسر، الفئة هي
فئات النصف الأيسر هي \(L=0,1,2\): الفئة \(L=0\) تعني أن \(m-2\) و\(m-1\) غير مختارين، والفئة \(L=1\) تعني أن آخر اختيار هو \(m-2\)، والفئة \(L=2\) تعني أن آخر اختيار هو \(m-1\).
وبالنسبة إلى النصف الأيمن، الفئة هي
فئات النصف الأيمن هي \(R=0,1,2\): الفئة \(R=0\) تعني أن \(m\) و\(m+1\) غير مختارين، والفئة \(R=1\) تعني أن أول اختيار هو \(m+1\)، والفئة \(R=2\) تعني أن أول اختيار هو \(m\).
إذا كانت فئة اليسار \(0\)، فلا يوجد تعارض حدودي. إذا كانت \(1\)، فإن فئة اليمين \(2\) فقط قريبة جداً. إذا كانت \(2\)، فإن \(m\) و\(m+1\) كلاهما قريبان جداً، لذلك يسمح فقط بفئة اليمين \(0\). قاعدة التوافق هذه هي بالضبط شرط \(|i-j|\ge3\) عبر الحد.
build_powers يبني الأزواج \((a_i,b_i)\) لتمثيل \(x^i=a_i+b_i x\). وevaluate_positions يجمع هذه الأزواج لمجموعة مواضع منفردة مقترحة. أما singleton_positions فيحاكي عملية الحجارة مباشرة في حالات صغيرة، مما يتحقق من التمثيل الجبري ومن تفسير أثر الأحجار المنفردة.
enumerate_right يعدّد تكرارياً كل المجموعات الجزئية الصالحة في النصف الأيمن ذات الفجوة \(3\)، ويضعها في السلال الحدودية الثلاث. كل إدخال يحتوي على المعامل المختزل والثابت. build_left_tasks ينشئ بادئات يسارية قصيرة؛ وتستخدم نسخة C++ هذه البادئات لتوزيع البحث اليساري الأعمق على عدة خيوط تنفيذ.
combine_left_dfs يكمل كل مجموعة جزئية يسارية، يحسب فئتها الحدودية، ولا يستعلم إلا السلال اليمنى المتوافقة. تقبل المطابقة عندما تتلاشى المعاملات ويكون مجموع الثوابت موجباً. هذا الثابت الموجب يضاف إلى الجواب لأنه قيمة البداية الممثلة.
مجموعة الاختبارات تتحقق من الآثار المعروفة لـ \(n=1\)، و\(n=68\)، و\(n=90\)، ثم تتحقق من \(S(14)=159\) و\(S(30)=33438\). بعد ذلك فقط يحسب البرنامج \(S(80)\).
البحث غير المقسوم سيفحص \(F(k)\) مجموعة جزئية صالحة، وهذا غير عملي عند \(k=80\). طريقة meet-in-the-middle تخزن \(O(F(k/2))\) حالة في النصف الأيمن، وتجري \(O(F(k/2))\) عمليات بحث في النصف الأيسر.
في نسخة C++ ذات الجداول المرتبة، بناء الجداول اليمنى يكلف \(O(F(k/2)\log F(k/2))\)، وكل مجموعة يسارية مكتملة تجري عدداً ثابتاً من عمليات البحث الثنائي. نسختا Python وJava المعتمدتان على الجداول لهما زمن بناء متوقع \(O(F(k/2))\) وزمن استعلام متوقع ثابت في المجال الفعلي \(k\le80\). استخدام الذاكرة هو \(O(F(k/2))\).