The bowls start with a deterministic pseudo-random number of beans. A legal move chooses a bowl containing at least two beans, removes two beans from it, and places one bean in each neighboring bowl. The task is to count how many such spills occur before every bowl contains at most one bean.
Index the bowls by integers and let \(b_i\) be the number of beans in bowl \(i\). Although the input generator only produces finitely many nonzero bowls, the process is best viewed on the whole integer line, because beans may move left of the original range.
The code tracks three global quantities:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
Here \(B\) is the total number of beans, \(M_1\) is the first moment, and \(M_2\) is the second moment. One spill at position \(i\) changes the state by
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
The bean count is preserved because \(-2+1+1=0\). The first moment is also preserved because
$$(-2)\,i + (i-1) + (i+1) = 0.$$
Therefore every reachable configuration has the same values of \(B\) and \(M_1\) as the initial one.
The decisive simplification is that every legal spill changes \(M_2\) by the same amount:
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
Hence the total number of moves depends only on the initial and final second moments:
$$\#\text{moves}=\frac{M_2^{\text{final}}-M_2^{\text{initial}}}{2}.$$
So the problem is no longer “simulate all spills”, but “identify the stabilized state and compute its second moment”.
A bowl is unstable exactly when it contains at least two beans. Therefore every stabilized state satisfies \(b_i\in\{0,1\}\) for all \(i\). The final state is thus a set of \(B\) occupied integer positions.
Write these occupied positions as
$$x_0<x_1<\cdots<x_{B-1}.$$
Because the first moment is invariant, they must satisfy
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
Among all such \(0/1\)-configurations, stabilization for this one-dimensional spill rule leads to the one with smallest possible second moment \(\sum_j x_j^2\). That is the quantity reconstructed by the code.
Subtract the baseline ordering by defining \(x_j=j+y_j\). Since the \(x_j\) are strictly increasing integers, the sequence \(y_0,\dots,y_{B-1}\) is nondecreasing. Its total is
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
Now minimize \(\sum_j (j+y_j)^2\) subject to this fixed sum. Because the square function is convex, the minimum is achieved when the \(y_j\) are as equal as possible. Therefore each optimal \(y_j\) must be either \(q\) or \(q+1\), where
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
So \(B-r\) of the adjusted values equal \(q\), and the remaining \(r\) equal \(q+1\). Translating back gives
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
Equivalently, the occupied bowls are
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
namely one almost-consecutive block with exactly one missing position. This is the final pattern encoded by the implementation.
Because \(\text{target\_shift}\) can be negative, the C++ solution uses a custom floor-division helper instead of relying on truncation toward zero.
The solver does not enumerate final positions one by one. It uses the arithmetic square-sum identity
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
Let
$$n_1=B-r,\qquad n_2=r.$$
Then the two occupied blocks start at \(q\) and \(q+n_1+1\), so
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
This is exactly what the helper sum_squares_arith(first, n) computes.
The source includes a small verification case with two bowls containing \([2,3]\). Using indices \(0,1\):
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
Then
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
Hence the final occupied positions are \(-2,-1,1,2,3\), whose second moment is
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
Therefore
$$\#\text{moves}=\frac{19-3}{2}=8,$$
which matches the checkpoint in the code.
The implementation has three compact stages. First, generate_beans(count) creates the deterministic initial configuration. Second, moves_needed(beans) scans the input once and accumulates \(B\), \(M_1\), and \(M_2\). Third, it reconstructs the optimal stabilized pattern from \((q,r)\), evaluates \(M_2^{\text{final}}\) with two arithmetic square sums, and returns \((M_2^{\text{final}}-M_2^{\text{initial}})/2\).
No step-by-step spill simulation is performed anywhere.
If the generator produces \(N\) initial bowls, the moment accumulation costs \(O(N)\) time. Everything after that is \(O(1)\). Extra memory is \(O(1)\) beyond the input container. This is dramatically better than simulating every spill, because the actual number of moves is extremely large.
Die Schalen erhalten anfangs eine deterministisch pseudozufaellige Anzahl von Bohnen. Ein legaler Zug waehlt eine Schale mit mindestens zwei Bohnen, entfernt daraus zwei Bohnen und legt je eine Bohne in die linke und rechte Nachbarschale. Gesucht ist die Anzahl solcher Spill-Schritte bis jede Schale hoechstens eine Bohne enthaelt.
Nummeriere die Schalen mit ganzen Zahlen und sei \(b_i\) die Belegung der Schale \(i\). Obwohl der Generator nur endlich viele anfangs nichtleere Schalen liefert, betrachtet man den Prozess am besten auf der ganzen Zahlengeraden, weil Bohnen nach links aus dem urspruenglichen Bereich wandern koennen.
Der Code sammelt drei globale Groessen:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
Dabei ist \(B\) die Gesamtzahl der Bohnen, \(M_1\) der erste Moment und \(M_2\) der zweite Moment. Ein Spill an Position \(i\) bewirkt
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
Die Gesamtzahl bleibt erhalten, weil \(-2+1+1=0\). Auch der erste Moment bleibt invariant, denn
$$(-2)\,i + (i-1) + (i+1) = 0.$$
Also besitzen alle erreichbaren Konfigurationen dieselben Werte von \(B\) und \(M_1\) wie die Startverteilung.
Die entscheidende Beobachtung ist, dass jeder legale Spill \(M_2\) um denselben Betrag veraendert:
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
Damit haengt die Gesamtzahl der Zuege nur vom Anfangs- und Endwert des zweiten Moments ab:
$$\#\text{Zuege}=\frac{M_2^{\text{final}}-M_2^{\text{initial}}}{2}.$$
Das Problem ist daher nicht mehr die explizite Simulation aller Spill-Schritte, sondern die Bestimmung des stabilen Endzustands und seines zweiten Moments.
Eine Schale ist genau dann instabil, wenn sie mindestens zwei Bohnen enthaelt. In jedem stabilen Zustand gilt also \(b_i\in\{0,1\}\) fuer alle \(i\). Der Endzustand ist folglich einfach eine Menge von \(B\) besetzten ganzzahligen Positionen.
Schreibe diese Positionen als
$$x_0<x_1<\cdots<x_{B-1}.$$
Wegen der Invarianz von \(M_1\) muss gelten
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
Unter allen solchen \(0/1\)-Belegungen fuehrt die Stabilisierung bei dieser eindimensionalen Spill-Regel zu derjenigen mit minimalem zweiten Moment \(\sum_j x_j^2\). Genau diese Groesse rekonstruiert der Code.
Ziehe die Basisordnung ab und setze \(x_j=j+y_j\). Da die \(x_j\) strikt wachsende ganze Zahlen sind, ist die Folge \(y_0,\dots,y_{B-1}\) nicht fallend. Ihre Summe ist
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
Nun minimiert man \(\sum_j (j+y_j)^2\) bei festem Gesamtwert. Wegen der Konvexitaet der Quadratfunktion wird das Minimum erreicht, wenn die \(y_j\) moeglichst gleich verteilt sind. Daher kann in einer optimalen Loesung jedes \(y_j\) nur \(q\) oder \(q+1\) sein, wobei
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
Somit sind \(B-r\) der angepassten Werte gleich \(q\), und die restlichen \(r\) gleich \(q+1\). Rueckuebersetzt erhaelt man
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
Aequivalent dazu sind die besetzten Schalen
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
also fast ein zusammenhaengender Block mit genau einer Luecke. Genau diese Struktur baut die Implementierung auf.
Weil \(\text{target\_shift}\) negativ sein kann, verwendet die C++-Version eine eigene Floor-Division statt einer Division mit Abschneiden gegen null.
Der Solver listet die Endpositionen nicht einzeln auf. Er benutzt die Quadratsummenformel fuer eine arithmetische Folge:
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
Mit
$$n_1=B-r,\qquad n_2=r$$
beginnen die beiden besetzten Bloecke bei \(q\) und \(q+n_1+1\). Also gilt
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
Genau das berechnet die Hilfsfunktion sum_squares_arith(first, n).
Im Quelltext gibt es einen kleinen Testfall mit zwei Schalen \([2,3]\). Fuer die Indizes \(0,1\) gilt:
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
Dann folgt
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
Damit sind die Endpositionen \(-2,-1,1,2,3\) und ihr zweiter Moment ist
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
Somit
$$\#\text{Zuege}=\frac{19-3}{2}=8,$$
genau wie im Checkpoint des Programms.
Die Implementierung besteht aus drei kompakten Schritten. Erstens erzeugt generate_beans(count) die deterministische Startbelegung. Zweitens durchlaeuft moves_needed(beans) das Array genau einmal und akkumuliert \(B\), \(M_1\) und \(M_2\). Drittens rekonstruiert der Code aus \((q,r)\) das optimale stabile Muster, berechnet \(M_2^{\text{final}}\) ueber zwei Quadratsummen arithmetischer Folgen und gibt \((M_2^{\text{final}}-M_2^{\text{initial}})/2\) zurueck.
Eine schrittweise Spill-Simulation findet nirgends statt.
Wenn der Generator \(N\) anfaengliche Schalen liefert, kostet die Berechnung von \(B\), \(M_1\) und \(M_2\) \(O(N)\) Zeit. Alles danach ist \(O(1)\). Der Zusatzspeicher ist \(O(1)\) jenseits des Eingabearrays. Das ist in der Praxis um Groessenordnungen besser als die Simulation aller Zuege, weil deren Anzahl extrem gross ist.
Kaplar başlangıçta deterministik ama sözde rastgele bir kuralla üretilen sayıda fasulye içerir. Geçerli bir hamlede en az iki fasulye içeren bir kaptan iki fasulye alınır ve komşu iki kaba birer fasulye bırakılır. Amaç, tüm kaplarda en fazla bir fasulye kalana kadar kaç taşma hamlesi yapıldığını bulmaktır.
Kapları tam sayılarla indeksleyelim ve \(b_i\), \(i\). kaptaki fasulye sayısı olsun. Girdi üreteci yalnızca sonlu sayıda dolu kap üretse de süreç en iyi tüm tam sayı doğrusu üzerinde düşünülür; çünkü fasulyeler başlangıç aralığının soluna da hareket edebilir.
Kod üç global nicelik toplar:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
Burada \(B\) toplam fasulye sayısı, \(M_1\) birinci moment, \(M_2\) ise ikinci momenttir. \(i\) konumundaki bir taşma hamlesi şu güncellemeyi yapar:
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
Toplam fasulye sayısı korunur; çünkü \(-2+1+1=0\). Birinci moment de korunur; çünkü
$$(-2)\,i + (i-1) + (i+1) = 0.$$
Dolayısıyla ulaşılabilen her durum başlangıçtaki \(B\) ve \(M_1\) değerleriyle aynı değerlere sahiptir.
Asıl sadeleştirme şudur: her geçerli taşma hamlesi \(M_2\)'yi aynı miktarda değiştirir.
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
Böylece toplam hamle sayısı yalnızca başlangıç ve son ikinci momentlere bağlı olur:
$$\#\text{hamle}=\frac{M_2^{\text{son}}-M_2^{\text{ilk}}}{2}.$$
Yani problem artık tüm taşmaları simüle etmek değil, stabil son durumu tanımlayıp onun ikinci momentini hesaplamaktır.
Bir kap tam olarak en az iki fasulye içerdiğinde kararsızdır. O halde her stabil durumda tüm \(i\) için \(b_i\in\{0,1\}\) olmalıdır. Başka bir deyişle son durum, üzerinde tam \(B\) tane dolu konum bulunan bir tamsayı kümesidir.
Bu dolu konumları
$$x_0<x_1<\cdots<x_{B-1}$$
şeklinde yazalım. Birinci moment korunduğu için
$$x_0+x_1+\cdots+x_{B-1}=M_1$$
olmalıdır. Bu tek boyutlu taşma kuralında stabilizasyonda ulaşılan son düzen, bu kısıtları sağlayan ve \(\sum_j x_j^2\) değerini en küçük yapan \(0/1\) yerleşimidir. Kodun yeniden kurduğu yapı tam olarak budur.
Temel sıralamayı çıkarıp \(x_j=j+y_j\) yazalım. \(x_j\)'ler artan tamsayılar olduğundan \(y_0,\dots,y_{B-1}\) dizisi azalmayandır. Toplamları
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}$$
olur. Şimdi sabit toplam altında \(\sum_j (j+y_j)^2\) ifadesini minimize ediyoruz. Kare fonksiyonu konveks olduğu için minimum, \(y_j\) değerleri olabildiğince birbirine yakın olduğunda elde edilir. Bu yüzden optimal durumda her \(y_j\) yalnızca \(q\) veya \(q+1\) olabilir; burada
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
Buna göre \(B-r\) adet değer \(q\), kalan \(r\) adet değer ise \(q+1\) olur. Geri dönüştürürsek
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
Eşdeğer olarak dolu kaplar
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B$$
şeklindedir; yani neredeyse ardışık olan ama tam bir yerde boşluk bırakan tek blok oluşur. Kodun kurduğu son yapı budur.
\(\text{target\_shift}\) negatif olabildiği için C++ çözümü normal bölme yerine gerçek taban yuvarlaması yapan özel bir floor_div yordamı kullanır.
Çözücü son konumları tek tek dolaşmaz. Bunun yerine aritmetik dizide kareler toplamı özdeşliğini kullanır:
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
Şimdi
$$n_1=B-r,\qquad n_2=r$$
olsun. İki dolu blok sırasıyla \(q\) ve \(q+n_1+1\) konumlarından başladığı için
$$M_2^{\text{son}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
Bu formülü kodda sum_squares_arith(first, n) yardımcı fonksiyonu uygular.
Kaynak kodda iki kaplı \([2,3]\) örneğiyle bir doğrulama yapılır. İndeksler \(0,1\) olunca
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
Buradan
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3$$
elde edilir. Son dolu konumlar \(-2,-1,1,2,3\) olur ve ikinci momentleri
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19$$
çıkar. O halde
$$\#\text{hamle}=\frac{19-3}{2}=8,$$
ki bu da koddaki kontrol sonucuyla aynıdır.
Uygulama üç kısa aşamadan oluşur. İlk olarak generate_beans(count) deterministik başlangıç dizisini üretir. Sonra moves_needed(beans) girdiyi tek geçişte tarayıp \(B\), \(M_1\) ve \(M_2\) değerlerini toplar. Son aşamada \((q,r)\) parametrelerinden optimal stabil desen yeniden kurulur, iki aritmetik kare toplamıyla \(M_2^{\text{son}}\) hesaplanır ve \((M_2^{\text{son}}-M_2^{\text{ilk}})/2\) döndürülür.
Hiçbir yerde adım adım taşma simülasyonu yapılmaz.
Üreteç \(N\) adet başlangıç kabı veriyorsa \(B\), \(M_1\) ve \(M_2\) toplama maliyeti \(O(N)\) zamandır. Bundan sonrası \(O(1)\)'dir. Girdi dizisi dışında ek bellek \(O(1)\)'dir. Gerçek hamle sayısı aşırı büyük olduğundan bu yaklaşım, tüm taşmaları simüle etmeye göre pratikte çok daha üstündür.
Los recipientes empiezan con una cantidad de frijoles generada por una regla pseudoaleatoria determinista. Un movimiento legal elige un recipiente con al menos dos frijoles, quita dos frijoles de ese recipiente y coloca uno en cada vecino. La tarea consiste en contar cuántos derrames ocurren hasta que todos los recipientes contienen como máximo un frijol.
Indexemos los recipientes por enteros y sea \(b_i\) el número de frijoles en la posición \(i\). Aunque el generador produce solo un número finito de recipientes inicialmente no vacíos, conviene pensar el proceso sobre toda la recta entera, porque los frijoles pueden desplazarse a la izquierda del intervalo original.
El código acumula tres cantidades globales:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
Aquí \(B\) es el número total de frijoles, \(M_1\) es el primer momento y \(M_2\) el segundo momento. Un derrame en la posición \(i\) actualiza el estado como
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
La cantidad total se conserva porque \(-2+1+1=0\). El primer momento también permanece constante, ya que
$$(-2)\,i + (i-1) + (i+1) = 0.$$
Por tanto, toda configuración alcanzable comparte los mismos valores de \(B\) y \(M_1\) que la configuración inicial.
La observación clave es que cada derrame legal modifica \(M_2\) en una cantidad fija:
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
De ahí se sigue que el número total de movimientos depende solo de los segundos momentos inicial y final:
$$\#\text{movimientos}=\frac{M_2^{\text{final}}-M_2^{\text{inicial}}}{2}.$$
Así, el problema deja de ser “simular todos los derrames” y pasa a ser “describir el estado estable y calcular su segundo momento”.
Un recipiente es inestable exactamente cuando contiene al menos dos frijoles. Entonces, en cualquier estado estable se cumple \(b_i\in\{0,1\}\) para todo \(i\). El estado final es, por tanto, un conjunto de \(B\) posiciones enteras ocupadas.
Escribamos esas posiciones ocupadas como
$$x_0<x_1<\cdots<x_{B-1}.$$
Como el primer momento se conserva, deben satisfacer
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
Entre todas esas configuraciones \(0/1\), la estabilización para esta regla unidimensional conduce a la de menor segundo momento \(\sum_j x_j^2\). Esa es precisamente la cantidad que reconstruye el programa.
Restemos la ordenación base definiendo \(x_j=j+y_j\). Como los \(x_j\) son enteros estrictamente crecientes, la sucesión \(y_0,\dots,y_{B-1}\) es no decreciente. Su suma vale
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
Ahora debemos minimizar \(\sum_j (j+y_j)^2\) con suma fija. Como la función cuadrática es convexa, el mínimo se alcanza cuando los \(y_j\) son lo más iguales posible. Por ello, en una solución óptima cada \(y_j\) solo puede ser \(q\) o \(q+1\), donde
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
Así, \(B-r\) de los valores ajustados son \(q\) y los \(r\) restantes son \(q+1\). Volviendo a \(x_j\), obtenemos
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
De manera equivalente, los recipientes ocupados son
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
es decir, un bloque casi consecutivo con un único hueco. Esa es exactamente la forma final construida por la implementación.
Como \(\text{target\_shift}\) puede ser negativo, la versión en C++ usa una rutina explícita de división piso en vez de la división truncada hacia cero.
El solucionador no enumera las posiciones finales una por una. Usa la identidad para la suma de cuadrados en una progresión aritmética:
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
Sea
$$n_1=B-r,\qquad n_2=r.$$
Los dos bloques ocupados comienzan en \(q\) y \(q+n_1+1\), de modo que
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
Eso es exactamente lo que implementa la función auxiliar sum_squares_arith(first, n).
El código incluye un caso de verificación con dos recipientes \([2,3]\). Usando índices \(0,1\):
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
Entonces
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
Las posiciones finales ocupadas son \(-2,-1,1,2,3\), y su segundo momento es
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
Por tanto,
$$\#\text{movimientos}=\frac{19-3}{2}=8,$$
exactamente el valor del checkpoint del programa.
La implementación tiene tres etapas compactas. Primero, generate_beans(count) crea la configuración inicial determinista. Segundo, moves_needed(beans) recorre la entrada una sola vez y acumula \(B\), \(M_1\) y \(M_2\). Tercero, reconstruye el patrón estable óptimo a partir de \((q,r)\), evalúa \(M_2^{\text{final}}\) mediante dos sumas cerradas de cuadrados y devuelve \((M_2^{\text{final}}-M_2^{\text{inicial}})/2\).
En ningún momento se simula derrame por derrame.
Si el generador produce \(N\) recipientes iniciales, acumular \(B\), \(M_1\) y \(M_2\) cuesta \(O(N)\) tiempo. Todo lo demás es \(O(1)\). La memoria adicional es \(O(1)\) aparte del contenedor de entrada. En la práctica, esto es muchísimo mejor que simular todos los derrames, porque el número real de movimientos es enorme.
每个碗中的豆子数由一个确定性的伪随机规则生成。一次合法操作会从某个至少有两颗豆子的碗里拿走两颗，并分别向左右相邻碗各放一颗。题目要求计算：直到所有碗都至多含一颗豆子为止，一共会发生多少次这样的“溢出”操作。
用整数给碗编号，记 \(b_i\) 为位置 \(i\) 上的豆子数。虽然输入生成器只给出有限个初始非零位置，但从数学上最好把整个过程看成发生在整条整数线上，因为豆子可能向初始区间左侧继续扩散。
代码累计三个全局量：
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
其中 \(B\) 是豆子总数，\(M_1\) 是一阶矩，\(M_2\) 是二阶矩。若在位置 \(i\) 发生一次溢出，则状态更新为
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
总豆子数保持不变，因为 \(-2+1+1=0\)。一阶矩也保持不变，因为
$$(-2)\,i + (i-1) + (i+1) = 0.$$
因此，所有可达状态都与初始状态拥有相同的 \(B\) 与 \(M_1\)。
最关键的观察是：每次合法溢出对 \(M_2\) 的改变量是常数。
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
于是总步数只由初末二阶矩决定：
$$\#\text{steps}=\frac{M_2^{\text{final}}-M_2^{\text{initial}}}{2}.$$
这就把问题从“逐步模拟全部溢出”转化成“找出稳定终态并计算其二阶矩”。
一个碗不稳定，当且仅当其中至少有两颗豆子。因此任何稳定状态都满足 \(b_i\in\{0,1\}\)。换句话说，终态只是 \(B\) 个被占据的整数位置组成的集合。
把这些被占据的位置记作
$$x_0<x_1<\cdots<x_{B-1}.$$
由于一阶矩保持不变，它们必须满足
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
对这条一维溢出规则而言，最终稳定态正是所有满足上述约束的 \(0/1\) 布局中二阶矩 \(\sum_j x_j^2\) 最小的那一个。代码就是在重建这个最优布局。
把基准顺序减掉，令 \(x_j=j+y_j\)。由于 \(x_j\) 是严格递增的整数，序列 \(y_0,\dots,y_{B-1}\) 必然单调不减。其总和为
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
现在的问题变成：在总和固定时最小化 \(\sum_j (j+y_j)^2\)。由于平方函数是凸函数，最优解一定让 \(y_j\) 尽量彼此接近。因此每个最优 \(y_j\) 只能取 \(q\) 或 \(q+1\)，其中
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
于是有 \(B-r\) 个值等于 \(q\)，其余 \(r\) 个值等于 \(q+1\)。还原到 \(x_j\) 后得到
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
等价地说，被占据的位置为
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
也就是几乎连续、但恰好缺一个位置的块。实现中构造的正是这个终态结构。
因为 \(\text{target\_shift}\) 可能为负，所以 C++ 版本专门实现了向下取整除法，而不是直接使用朝零截断的整数除法。
程序不会逐个枚举终态位置，而是使用等差数列平方和公式：
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
记
$$n_1=B-r,\qquad n_2=r.$$
两个占据块分别从 \(q\) 和 \(q+n_1+1\) 开始，因此
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
这正是辅助函数 sum_squares_arith(first, n) 所计算的内容。
源代码里包含一个两只碗 \([2,3]\) 的检查样例。若位置编号为 \(0,1\)，则
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
于是
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
终态占据位置为 \(-2,-1,1,2,3\)，其二阶矩为
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
因此
$$\#\text{steps}=\frac{19-3}{2}=8,$$
与源码中的 checkpoint 完全一致。
实现分为三步。第一步，generate_beans(count) 生成确定性的初始豆子分布。第二步，moves_needed(beans) 只扫描一次输入，就累计出 \(B\)、\(M_1\) 和 \(M_2\)。第三步，用 \((q,r)\) 重建最优稳定布局，用两段等差平方和求出 \(M_2^{\text{final}}\)，最后返回 \((M_2^{\text{final}}-M_2^{\text{initial}})/2\)。
整个过程中完全没有逐步模拟单次溢出。
若生成器产生 \(N\) 个初始碗，那么累计 \(B\)、\(M_1\)、\(M_2\) 的时间复杂度为 \(O(N)\)。之后所有计算都是 \(O(1)\)。除输入容器外，额外空间复杂度为 \(O(1)\)。相比真正去模拟所有溢出步骤，这个方法在实际中高效得多，因为总步数会非常巨大。
Изначально в чашах лежит количество бобов, заданное детерминированным псевдослучайным правилом. Законный ход выбирает чашу, где не меньше двух бобов, убирает из нее два боба и кладет по одному в левую и правую соседние чаши. Нужно посчитать, сколько таких проливов произойдет до тех пор, пока в каждой чаше не останется не более одного боба.
Нумеруем чаши целыми числами и обозначаем через \(b_i\) число бобов в позиции \(i\). Хотя генератор задает лишь конечное число ненулевых начальных чаш, процесс удобнее рассматривать на всей целочисленной прямой, поскольку бобы могут уйти левее исходного диапазона.
Код накапливает три глобальные величины:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
Здесь \(B\) — общее число бобов, \(M_1\) — первый момент, а \(M_2\) — второй момент. Один пролив в позиции \(i\) меняет состояние так:
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
Полное число бобов сохраняется, потому что \(-2+1+1=0\). Первый момент тоже сохраняется, поскольку
$$(-2)\,i + (i-1) + (i+1) = 0.$$
Следовательно, любая достижимая конфигурация имеет те же значения \(B\) и \(M_1\), что и начальная.
Ключевое упрощение состоит в том, что любой законный пролив меняет \(M_2\) на одну и ту же величину:
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
Значит, общее число ходов зависит только от начального и конечного вторых моментов:
$$\#\text{ходов}=\frac{M_2^{\text{final}}-M_2^{\text{initial}}}{2}.$$
Тем самым задача сводится не к пошаговой симуляции, а к нахождению устойчивой финальной конфигурации и ее второго момента.
Чаша неустойчива тогда и только тогда, когда в ней лежит не меньше двух бобов. Поэтому в любом устойчивом состоянии выполняется \(b_i\in\{0,1\}\) для всех \(i\). Иначе говоря, финальная конфигурация — это просто набор из \(B\) занятых целочисленных позиций.
Обозначим их через
$$x_0<x_1<\cdots<x_{B-1}.$$
Из инвариантности первого момента следует условие
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
Для данного одномерного правила пролива стабилизация приводит именно к той \(0/1\)-конфигурации, которая при этих ограничениях минимизирует второй момент \(\sum_j x_j^2\). Именно ее и восстанавливает программа.
Вычтем базовый порядок и запишем \(x_j=j+y_j\). Поскольку \(x_j\) — строго возрастающие целые числа, последовательность \(y_0,\dots,y_{B-1}\) невозрастающей быть не может, то есть она монотонно неубывает. Ее сумма равна
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
Теперь нужно минимизировать \(\sum_j (j+y_j)^2\) при фиксированной сумме. Так как квадрат — выпуклая функция, минимум достигается, когда значения \(y_j\) максимально выровнены. Поэтому в оптимуме каждый \(y_j\) может быть только \(q\) или \(q+1\), где
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
Значит, \(B-r\) значений равны \(q\), а оставшиеся \(r\) — \(q+1\). Возвращаясь к \(x_j\), получаем
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
Эквивалентно этому занятые позиции имеют вид
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
то есть почти сплошной блок с ровно одной пустой позицией. Именно такую структуру строит реализация.
Поскольку \(\text{target\_shift}\) может быть отрицательным, версия на C++ использует собственную функцию floor-деления, а не стандартное усечение к нулю.
Решение не перечисляет конечные позиции по одной. Оно использует формулу суммы квадратов арифметической прогрессии:
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
Положим
$$n_1=B-r,\qquad n_2=r.$$
Тогда два занятых блока начинаются в точках \(q\) и \(q+n_1+1\), и потому
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
Ровно это вычисляет вспомогательная функция sum_squares_arith(first, n).
В исходнике есть маленькая проверка для двух чаш \([2,3]\). Если их индексы \(0,1\), то
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
Тогда
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
Финальные занятые позиции: \(-2,-1,1,2,3\), а их второй момент равен
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
Следовательно,
$$\#\text{ходов}=\frac{19-3}{2}=8,$$
что точно совпадает с checkpoint в коде.
Реализация состоит из трех компактных частей. Сначала generate_beans(count) строит детерминированную начальную конфигурацию. Затем moves_needed(beans) одним проходом накапливает \(B\), \(M_1\) и \(M_2\). После этого программа восстанавливает оптимальный устойчивый шаблон через \((q,r)\), вычисляет \(M_2^{\text{final}}\) как сумму двух арифметических квадратных сумм и возвращает \((M_2^{\text{final}}-M_2^{\text{initial}})/2\).
Пошаговая симуляция проливов нигде не выполняется.
Если генератор выдает \(N\) начальных чаш, то накопление \(B\), \(M_1\) и \(M_2\) требует \(O(N)\) времени. Все последующие вычисления занимают \(O(1)\). Дополнительная память сверх входного контейнера — \(O(1)\). На практике это несравнимо лучше прямой симуляции, потому что число реальных ходов огромно.
تبدأ الأوعية بعدد من الحبوب مولَّد بطريقة شبه عشوائية حتمية. في كل حركة قانونية نختار وعاءً يحتوي على حبّتين على الأقل، نزيل منه حبّتين، ثم نضع حبّة واحدة في كل وعاء مجاور يمينًا ويسارًا. المطلوب هو حساب عدد هذه الحركات حتى تصبح كل الأوعية تحتوي على حبّة واحدة كحد أقصى.
لنرقّم الأوعية بالأعداد الصحيحة، ولتكن \(b_i\) هي كمية الحبوب في الوعاء ذي الفهرس \(i\). مع أن المولّد يعطي عددًا منتهيًا من الأوعية غير الفارغة في البداية، فمن الأفضل رياضيًا أن ننظر إلى العملية على خط الأعداد الصحيح كله، لأن الحبوب قد تنتقل إلى يسار المجال الابتدائي.
يجمع الكود ثلاث كميات كلية:
$$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$
تمثل \(B\) العدد الكلي للحبوب، ويمثل \(M_1\) العزم الأول، ويمثل \(M_2\) العزم الثاني. إذا حدث انسكاب عند الموضع \(i\)، فإن التحديث يكون
$$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$
يبقى عدد الحبوب ثابتًا لأن \(-2+1+1=0\). ويبقى العزم الأول ثابتًا أيضًا لأن
$$(-2)\,i + (i-1) + (i+1) = 0.$$
إذن كل حالة يمكن الوصول إليها لها نفس القيمتين \(B\) و\(M_1\) اللتين لدى الحالة الابتدائية.
الفكرة الحاسمة هي أن كل حركة انسكاب قانونية تغيّر \(M_2\) بالمقدار نفسه دائمًا:
$$\Delta M_2=(i-1)^2+(i+1)^2-2i^2=2.$$
ومن ثم فإن عدد الحركات الكلي يعتمد فقط على العزم الثاني في البداية والنهاية:
$$\#\text{الحركات}=\frac{M_2^{\text{final}}-M_2^{\text{initial}}}{2}.$$
وبهذا تتحول المسألة من محاكاة جميع الانسكابات خطوة بخطوة إلى تحديد الحالة المستقرة النهائية وحساب عزمها الثاني.
يكون الوعاء غير مستقر إذا وفقط إذا احتوى على حبّتين على الأقل. لذلك في أي حالة مستقرة لا بد أن يتحقق \(b_i\in\{0,1\}\) لكل \(i\). أي إن الحالة النهائية ليست إلا مجموعة من \(B\) مواضع صحيحة مشغولة.
لنكتب هذه المواضع المشغولة على الصورة
$$x_0<x_1<\cdots<x_{B-1}.$$
وبما أن العزم الأول ثابت، فلا بد أن تحقق
$$x_0+x_1+\cdots+x_{B-1}=M_1.$$
بالنسبة إلى قاعدة الانسكاب الأحادية البعد هذه، فإن التثبيت يصل إلى ترتيب \(0/1\) الذي يصغّر العزم الثاني \(\sum_j x_j^2\) تحت هذه القيود. وهذا هو الترتيب الذي يعيد الكود بناءه.
لنطرح الترتيب الأساسي ونكتب \(x_j=j+y_j\). بما أن \(x_j\) أعداد صحيحة متزايدة تمامًا، فإن المتتالية \(y_0,\dots,y_{B-1}\) غير متناقصة. ومجموعها هو
$$\sum_{j=0}^{B-1} y_j = M_1-\sum_{j=0}^{B-1}j = M_1-\frac{B(B-1)}{2}=: \text{target\_shift}.$$
الآن نريد تصغير \(\sum_j (j+y_j)^2\) مع ثبات المجموع. وبسبب تحدب دالة التربيع، يتحقق الحد الأدنى عندما تكون قيم \(y_j\) متقاربة قدر الإمكان. لذلك لا يمكن أن يأخذ \(y_j\) الأمثل إلا إحدى القيمتين \(q\) أو \(q+1\)، حيث
$$q=\left\lfloor\frac{\text{target\_shift}}{B}\right\rfloor,\qquad r=\text{target\_shift}-qB,\qquad 0\le r<B.$$
وعليه فهناك \(B-r\) قيمة تساوي \(q\)، و\(r\) قيم تساوي \(q+1\). وبالرجوع إلى \(x_j\) نحصل على
$$x_j=j+q\quad (0\le j<B-r),\qquad x_j=j+q+1\quad (B-r\le j<B).$$
وبصيغة مكافئة تكون المواضع المشغولة هي
$$q,\ q+1,\ \dots,\ q+(B-r)-1,\ q+(B-r)+1,\ \dots,\ q+B,$$
أي كتلة شبه متتالية تحتوي على فجوة واحدة بالضبط. هذه هي البنية النهائية التي ينشئها التنفيذ.
ولأن \(\text{target\_shift}\) قد يكون سالبًا، فإن نسخة ++C تستخدم دالة قسمة أرضية مخصصة بدل الاعتماد على القسمة التي تقطع نحو الصفر.
لا يقوم الحل بتعداد المواضع النهائية واحدًا واحدًا، بل يستخدم متطابقة مجموع مربعات متتالية حسابية:
$$\sum_{k=0}^{n-1}(a+k)^2 = n a^2 + 2a\frac{n(n-1)}{2} + \frac{n(n-1)(2n-1)}{6}.$$
لنعرّف
$$n_1=B-r,\qquad n_2=r.$$
عندئذ تبدأ الكتلتان المشغولتان عند \(q\) و\(q+n_1+1\)، ومن ثم
$$M_2^{\text{final}}=\sum_{k=0}^{n_1-1}(q+k)^2+\sum_{k=0}^{n_2-1}(q+n_1+1+k)^2.$$
وهذا بالضبط ما تحسبه الدالة المساعدة sum_squares_arith(first, n).
يتضمن المصدر حالة فحص صغيرة مكوّنة من وعاءين بقيم \([2,3]\). إذا كانت الفهارس \(0,1\)، فإن
$$B=5,\qquad M_1=0\cdot2+1\cdot3=3,\qquad M_2=0^2\cdot2+1^2\cdot3=3.$$
إذًا
$$\text{target\_shift}=3-\frac{5\cdot4}{2}=-7,\qquad q=\left\lfloor\frac{-7}{5}\right\rfloor=-2,\qquad r=3.$$
فتكون المواضع النهائية المشغولة هي \(-2,-1,1,2,3\)، ويكون عزمها الثاني
$$(-2)^2+(-1)^2+1^2+2^2+3^2=19.$$
وبالتالي
$$\#\text{الحركات}=\frac{19-3}{2}=8,$$
وهو تمامًا ما يتحقق منه الكود.
يتكون التنفيذ من ثلاث مراحل موجزة. أولًا، تنشئ الدالة generate_beans(count) الحالة الابتدائية الحتمية. ثانيًا، تمر الدالة moves_needed(beans) مرة واحدة على المدخلات لتجميع \(B\) و\(M_1\) و\(M_2\). ثالثًا، يعيد البرنامج بناء النمط المستقر الأمثل عبر \((q,r)\)، ثم يحسب \(M_2^{\text{final}}\) باستخدام مجموعين مغلقين لمربعات متتالية حسابية، وأخيرًا يعيد \((M_2^{\text{final}}-M_2^{\text{initial}})/2\).
لا توجد أي محاكاة تفصيلية لحركات الانسكاب.
إذا ولّد المصدر \(N\) أوعية ابتدائية، فإن حساب \(B\) و\(M_1\) و\(M_2\) يستغرق زمنًا \(O(N)\). وما بعد ذلك كله \(O(1)\). والذاكرة الإضافية هي \(O(1)\) فوق حاوية الإدخال. وهذا أفضل عمليًا بكثير من محاكاة كل الانسكابات، لأن العدد الحقيقي للحركات ضخم جدًا.