A position is a line segment of length \(L\). A legal move chooses a square with side \(s\in\{1,\sqrt{2}\}\) and places its base on the segment, so the occupied interval has length \(s\). If the left edge is at \(x\), the move removes \([x,x+s]\) and leaves two independent subgames of lengths \(x\) and \(L-s-x\).
The C++, Python, and Java implementations analyze this as a Sprague-Grundy game. They then maximize the scaled average proportion of zero-xor moves
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
and return
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500).$$
Here \(m(u)\) is the total length of placements that split the remaining segment \(u\) into two subpositions with equal Grundy value. The task is therefore a continuous impartial-game calculation followed by a one-dimensional maximization problem.
The derivation has two layers. First we compute the Grundy function \(g(L)\) for a real segment length. Then we build a second function \(m(u)\) that counts how often a move lands on xor \(0\), and finally maximize the resulting explicit formula for \(e(L)\).
For \(0\le L<1\) no square fits, so the position is terminal and
$$g(L)=0.$$
For larger \(L\), a move of side \(s\in\{1,\sqrt{2}\}\) can start at any \(x\) with \(0\le x\le L-s\). The two remaining parts are independent, so the nimber of that move is
$$g(x)\oplus g(L-s-x).$$
Therefore
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$$
where the second set is absent when \(L<\sqrt{2}\). This is the usual Sprague-Grundy recurrence, except that the game parameter is a real length instead of an integer size.
Every move removes either \(1\) or \(\sqrt{2}\) from the total occupied length before the remainder is split. Starting from \(0\), the only lengths at which the move structure can change are sums built from these two generators:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
Because \(\sqrt{2}\) is irrational, different pairs \((a,b)\) produce different real numbers. After sorting these values, any open interval between consecutive breakpoints has the same interaction pattern with all earlier intervals shifted by \(1\) and by \(\sqrt{2}\). Hence the reachable xor-set stays constant throughout that interval, so \(g(L)\) is piecewise constant.
This is the structural simplification used by the implementations: instead of sampling arbitrary real lengths, they store merged intervals on which one Grundy value applies everywhere.
Fix a side length \(s\) and a segment length \(L\). A placement at \(x\) is strategically important when it leaves xor \(0\), because the next player then receives a \(P\)-position. The condition is
$$g(x)\oplus g(L-s-x)=0,$$
which is equivalent to
$$g(x)=g(L-s-x).$$
Let \(u=L-s\). The set of such placements has total length
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$$
Since the legal interval of left endpoints has length \(u\), the fraction of zero-xor placements for side \(s\) is
$$\frac{m(L-s)}{L-s}.$$
The objective function is exactly the average of those two fractions, scaled by \(L\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
Suppose two intervals \(I=[A,B]\) and \(J=[C,D]\) carry the same Grundy value. For a fixed \(u\), a point \(x\) contributes to \(m(u)\) when \(x\in I\) and \(u-x\in J\). Equivalently,
$$x\in I\cap [u-D,u-C].$$
So the contribution from this pair is the overlap length
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
As \(u\) varies, \(\lambda_{I,J}(u)\) is piecewise linear: it increases linearly, may stay flat, then decreases linearly. Its slope can only change when one endpoint meets another, namely at
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
Summing these trapezoidal contributions over all interval pairs with equal Grundy value yields a global piecewise-linear spline
$$m(u)=s_i u+c_i \qquad (u\in I_i).$$
Distinct intervals matter in both orders \((I,J)\) and \((J,I)\), so they receive double weight; a diagonal pair contributes once.
Once \(m(u)\) is piecewise linear, the function \(e(L)\) becomes elementary on every interval where both shifted arguments stay inside fixed spline pieces. If
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$$
then
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
A derivative with the same zeros as \(e'(L)\) is
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$$
Therefore every local maximum must occur at an interval endpoint or at an interior root of this expression. The continuous search on \([A,B]\) is reduced to a finite collection of one-dimensional root checks.
For every \(u<1\), no square fits on a segment of length \(u\), so \(g(u)=0\). Consequently, if \(0\le u\le 1\), then \(g(x)=g(u-x)=0\) for almost every \(x\in[0,u]\), and therefore
$$m(u)=u.$$
Now set \(L=2\). Then
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
For side \(1\), every placement leaves two subsegments whose total length is \(1\), so both subsegments stay below length \(1\) except at measure-zero endpoints; the xor is always \(0\). For side \(\sqrt{2}\), the remaining total length is already below \(1\), so again every placement gives xor \(0\). Hence
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
Substituting into the formula gives
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$$
which matches the first validation checkpoint used by the implementations.
The C++ and Java implementations follow the derivation directly. They first enumerate all breakpoints \(a+b\sqrt{2}\) up to the needed limit, sort them, and scan the resulting intervals from left to right. On each interval they evaluate the reachable xor-set at a midpoint, take the mex, and merge adjacent intervals whenever the Grundy value remains unchanged.
Next they regroup those intervals by Grundy value and form the piecewise-linear spline for \(m(u)\). Each same-Grundy interval pair contributes four event positions where the slope can change, so after sorting the events a single sweep reconstructs every linear piece \(s_i u+c_i\).
Finally they build the \(L\)-breakpoints induced by shifting spline boundaries by \(1\) and \(\sqrt{2}\). On each such interval, the implementation checks the endpoints, looks for sign changes in the derivative expression, and applies bisection when an interior critical point exists. The Python implementation is only a thin wrapper around the C++ solver, while the C++ version also verifies checkpoints before printing the final value, including \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\), and \(f(10,20)=5.99374121\).
Let \(B\) be the number of raw breakpoints \(a+b\sqrt{2}\) up to the search limit, and let \(S\) be the number of merged Grundy intervals after equal neighboring values are coalesced. Generating and sorting the raw breakpoints costs \(O(B\log B)\).
Building the piecewise-constant Grundy table is worst-case \(O(S^2)\), because each new interval may scan a substantial portion of the previously constructed intervals to collect reachable xor values. Constructing \(m(u)\) from equal-Grundy interval pairs is also quadratic in the interval count in the worst case: if \(n_k\) intervals carry Grundy value \(k\), then the pair generation cost is \(O\left(\sum_k n_k^2\right)\), followed by an event sort of the same order up to a logarithmic factor.
The final maximization pass is linear in the number of induced \(L\)-intervals, with only constant-time evaluations plus a fixed number of bisection iterations per interval. Memory usage is \(O(S+E)\), where \(E\) is the number of event records in the spline construction.
Eine Stellung ist ein Liniensegment der Länge \(L\). Ein legaler Zug wählt ein Quadrat mit Seitenlänge \(s\in\{1,\sqrt{2}\}\) und legt seine Basis auf das Segment, sodass ein Intervall der Länge \(s\) belegt wird. Liegt die linke Kante bei \(x\), so wird \([x,x+s]\) entfernt und es bleiben zwei unabhängige Teilspiele der Längen \(x\) und \(L-s-x\).
Die C++-, Python- und Java-Implementierungen behandeln das als Sprague-Grundy-Spiel. Danach maximieren sie den skalierten Mittelwert der Null-xor-Züge
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
und geben
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500)$$
zurück. Dabei ist \(m(u)\) die Gesamtlänge aller Platzierungen, die den verbleibenden Rest \(u\) in zwei Teilstellungen mit gleichem Grundy-Wert zerlegen. Die Aufgabe ist also eine kontinuierliche impartial-game-Analyse mit anschließender eindimensionaler Optimierung.
Die Herleitung hat zwei Ebenen. Zuerst bestimmen wir die Grundy-Funktion \(g(L)\) für reelle Segmentlängen. Danach bauen wir daraus eine zweite Funktion \(m(u)\), die Null-xor-Züge misst, und maximieren schließlich die explizite Formel für \(e(L)\).
Für \(0\le L<1\) passt kein Quadrat auf das Segment, also ist die Stellung terminal und
$$g(L)=0.$$
Für größere \(L\) kann ein Quadrat der Seitenlänge \(s\in\{1,\sqrt{2}\}\) an jeder Position \(x\) mit \(0\le x\le L-s\) platziert werden. Die beiden Restteile sind unabhängig, also hat dieser Zug den Nim-Wert
$$g(x)\oplus g(L-s-x).$$
Daraus folgt
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$$
wobei die zweite Menge fehlt, wenn \(L<\sqrt{2}\). Das ist die übliche Sprague-Grundy-Rekurrenz, nur dass der Spielparameter hier eine reelle Länge ist.
Jeder Zug entfernt vor dem Aufteilen entweder \(1\) oder \(\sqrt{2}\) an belegter Länge. Ausgehend von \(0\) können sich strukturelle Änderungen deshalb nur an Summen aus diesen beiden Generatoren ergeben:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
Da \(\sqrt{2}\) irrational ist, liefern verschiedene Paare \((a,b)\) verschiedene reelle Zahlen. Sortiert man diese Werte, dann besitzt jedes offene Intervall zwischen zwei aufeinanderfolgenden Breakpoints dasselbe Interaktionsmuster mit allen früheren Intervallen, verschoben um \(1\) beziehungsweise \(\sqrt{2}\). Daher bleibt die erreichbare xor-Menge dort konstant, also ist \(g(L)\) stückweise konstant.
Genau diese Vereinfachung nutzen die Implementierungen: Statt beliebige reelle Längen abzutasten, speichern sie zusammengefasste Intervalle, auf denen ein Grundy-Wert überall gilt.
Fixiere eine Seitenlänge \(s\) und eine Segmentlänge \(L\). Eine Platzierung bei \(x\) ist strategisch wichtig, wenn sie xor \(0\) hinterlässt, denn dann bekommt der nächste Spieler eine \(P\)-Position. Die Bedingung lautet
$$g(x)\oplus g(L-s-x)=0,$$
also äquivalent
$$g(x)=g(L-s-x).$$
Setze \(u=L-s\). Die Gesamtlänge solcher Platzierungen ist
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$$
Da das Intervall möglicher linker Endpunkte die Länge \(u\) hat, ist der Anteil der Null-xor-Platzierungen für die Seitenlänge \(s\)
$$\frac{m(L-s)}{L-s}.$$
Die Zielfunktion ist genau der Mittelwert dieser beiden Anteile, skaliert mit \(L\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
Angenommen, zwei Intervalle \(I=[A,B]\) und \(J=[C,D]\) tragen denselben Grundy-Wert. Für festes \(u\) trägt ein Punkt \(x\) genau dann zu \(m(u)\) bei, wenn \(x\in I\) und zugleich \(u-x\in J\) gilt. Äquivalent dazu ist
$$x\in I\cap [u-D,u-C].$$
Der Beitrag dieses Intervallpaares ist also die Überlappungslänge
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
Mit wachsendem \(u\) ist \(\lambda_{I,J}(u)\) stückweise linear: erst wächst der Wert linear, eventuell folgt ein flacher Teil, danach fällt er linear. Die Steigung kann sich nur ändern, wenn zwei Endpunkte aufeinandertreffen, also bei
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
Summiert man diese trapezförmigen Beiträge über alle Intervallpaare mit gleichem Grundy-Wert, erhält man eine globale stückweise lineare Spline-Funktion
$$m(u)=s_i u+c_i \qquad (u\in I_i).$$
Verschiedene Intervalle zählen in beiden Reihenfolgen \((I,J)\) und \((J,I)\), daher erhalten sie doppeltes Gewicht; ein diagonales Paar trägt einmal bei.
Sobald \(m(u)\) stückweise linear ist, wird \(e(L)\) auf jedem Intervall elementar, auf dem beide verschobenen Argumente in festen Spline-Stücken liegen. Gilt
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$$
dann folgt
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
Ein Ausdruck mit denselben Nullstellen wie \(e'(L)\) ist
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$$
Damit kann ein lokales Maximum nur an einem Intervallrand oder an einer inneren Nullstelle dieses Ausdrucks liegen. Die kontinuierliche Suche auf \([A,B]\) wird so auf endlich viele eindimensionale Wurzeltests reduziert.
Für jedes \(u<1\) passt kein Quadrat auf ein Segment der Länge \(u\), also ist \(g(u)=0\). Daher gilt für \(0\le u\le 1\) fast überall auf \([0,u]\): \(g(x)=g(u-x)=0\), und somit
$$m(u)=u.$$
Setze nun \(L=2\). Dann ist
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
Für die Seitenlänge \(1\) hinterlässt jede Platzierung zwei Teilsegmente mit Gesamtlänge \(1\), also bleiben beide bis auf Randpunkte vom Maß \(0\) unter Länge \(1\); das xor ist immer \(0\). Für die Seitenlänge \(\sqrt{2}\) liegt die verbleibende Gesamtlänge sogar schon unter \(1\), also entsteht ebenfalls immer xor \(0\). Daher
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
Eingesetzt ergibt das
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$$
genau wie im ersten Validierungspunkt der Implementierungen.
Die C++- und Java-Implementierungen folgen der Herleitung Schritt für Schritt. Zuerst erzeugen sie alle Breakpoints \(a+b\sqrt{2}\) bis zur benötigten Grenze, sortieren sie und durchlaufen die entstehenden Intervalle von links nach rechts. Auf jedem Intervall bestimmen sie die erreichbare xor-Menge an einem Mittelpunkt, berechnen den mex-Wert und verschmelzen benachbarte Intervalle, solange der Grundy-Wert gleich bleibt.
Danach gruppieren sie diese Intervalle nach Grundy-Wert und bauen daraus die stückweise lineare Spline-Funktion für \(m(u)\). Jedes Paar gleichwertiger Grundy-Intervalle erzeugt vier Ereignispositionen, an denen sich die Steigung ändern kann; nach dem Sortieren dieser Ereignisse rekonstruiert ein einziger Sweep alle linearen Stücke \(s_i u+c_i\).
Zum Schluss werden die \(L\)-Breakpoints erzeugt, die aus den Spline-Grenzen durch Verschiebung um \(1\) und \(\sqrt{2}\) entstehen. Auf jedem solchen Intervall prüft die Implementierung die Randpunkte, sucht nach Vorzeichenwechseln im Ableitungsausdruck und verwendet bei Bedarf Bisektion für innere kritische Punkte. Die Python-Implementierung ist lediglich eine dünne Hülle um den C++-Solver; die C++-Variante überprüft vor der Ausgabe außerdem Kontrollwerte wie \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\) und \(f(10,20)=5.99374121\).
Sei \(B\) die Anzahl der rohen Breakpoints \(a+b\sqrt{2}\) bis zur Suchgrenze und \(S\) die Anzahl der zusammengefassten Grundy-Intervalle nach dem Verschmelzen gleicher Nachbarn. Das Erzeugen und Sortieren der rohen Breakpoints kostet \(O(B\log B)\).
Der Aufbau der stückweise konstanten Grundy-Tabelle ist im Worst Case \(O(S^2)\), weil jedes neue Intervall einen großen Teil der bereits konstruierten Intervalle scannen kann, um alle erreichbaren xor-Werte zu sammeln. Auch der Aufbau von \(m(u)\) aus Paaren gleichwertiger Grundy-Intervalle ist im schlimmsten Fall quadratisch: Tragen \(n_k\) Intervalle den Grundy-Wert \(k\), dann kostet die Paarbildung \(O\left(\sum_k n_k^2\right)\), gefolgt von einer Ereignissortierung derselben Größenordnung bis auf einen logarithmischen Faktor.
Der letzte Maximierungslauf ist linear in der Anzahl der induzierten \(L\)-Intervalle und benötigt pro Intervall nur konstante viele Auswertungen sowie eine feste Zahl von Bisektionsschritten. Der Speicherverbrauch ist \(O(S+E)\), wobei \(E\) die Zahl der Ereigniseinträge beim Aufbau der Spline-Funktion bezeichnet.
Bir konum, uzunluğu \(L\) olan bir doğru parçasıdır. Geçerli bir hamle, kenarı \(s\in\{1,\sqrt{2}\}\) olan bir kare seçer ve tabanını bu doğru parçası üzerine yerleştirir; yani kaplanan aralık uzunluğu \(s\) olur. Sol uç \(x\) noktasındaysa \([x,x+s]\) kaldırılır ve uzunlukları \(x\) ile \(L-s-x\) olan iki bağımsız alt oyun kalır.
C++, Python ve Java implementasyonları bu yapıyı bir Sprague-Grundy oyunu olarak ele alır. Daha sonra sıfır-xor bırakan hamlelerin ölçeklenmiş ortalama oranını
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right)$$
maksimize eder ve
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500)$$
değerini döndürür. Burada \(m(u)\), kalan toplam uzunluğu \(u\) olan durumda eşit Grundy değerli iki alt konum bırakan yerleştirmelerin toplam uzunluğudur. Dolayısıyla görev, sürekli bir impartial-game hesabını tek değişkenli bir maksimum problemine dönüştürmektir.
Türetim iki katmandan oluşur. Önce reel uzunluklar üzerinde Grundy fonksiyonu \(g(L)\) hesaplanır. Sonra buradan sıfır-xor hamlelerini ölçen \(m(u)\) fonksiyonu kurulur ve en son \(e(L)\) için elde edilen açık form maksimize edilir.
\(0\le L<1\) için hiçbir kare sığmaz; dolayısıyla konum terminaldir ve
$$g(L)=0.$$
Daha büyük \(L\) değerlerinde, kenarı \(s\in\{1,\sqrt{2}\}\) olan bir kare \(0\le x\le L-s\) aralığındaki herhangi bir başlangıç noktasına yerleştirilebilir. Kalan iki parça bağımsız olduğu için bu hamlenin nim değeri
$$g(x)\oplus g(L-s-x)$$
olur. O halde
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr)$$
yazılır; ikinci küme yalnızca \(L\ge\sqrt{2}\) iken vardır. Bu, klasik Sprague-Grundy bağıntısının reel uzunluk değişkenli halidir.
Her hamle, kalanın bölünmesinden önce toplam kaplanan uzunluktan ya \(1\) ya da \(\sqrt{2}\) çıkarır. Başlangıç noktası \(0\) olduğuna göre oyunun kombinatoryal yapısı ancak bu iki üreteçten oluşan toplamlar üzerinde değişebilir:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
\(\sqrt{2}\) irrasyonel olduğu için farklı \((a,b)\) çiftleri farklı reel sayılar verir. Bu değerler sıralandığında, ardışık iki kırılma noktası arasındaki açık aralık, daha önce oluşmuş aralıkların \(1\) ve \(\sqrt{2}\) kadar kaydırılmış kopyalarıyla aynı etkileşim desenine sahip olur. Bu nedenle erişilebilir xor kümesi tüm aralık boyunca sabittir; yani \(g(L)\) parça sabittir.
İmplementasyonların kullandığı temel sadeleştirme budur: keyfi reel uzunlukları örneklemek yerine, tek bir Grundy değerinin geçerli olduğu birleşik aralıklar tutulur.
Bir kenar uzunluğu \(s\) ve bir toplam uzunluk \(L\) sabitleyelim. \(x\) konumundaki bir yerleştirme, xor sonucu \(0\) bırakıyorsa stratejik olarak özeldir; çünkü sıradaki oyuncu bir \(P\)-konumu alır. Koşul
$$g(x)\oplus g(L-s-x)=0$$
olup bu da
$$g(x)=g(L-s-x)$$
ile aynıdır. \(u=L-s\) tanımını yapalım. Böyle yerleştirmelerin toplam uzunluğu
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right)$$
şeklindedir. Sol uç için geçerli aralığın uzunluğu \(u\) olduğundan, kenarı \(s\) olan kare için sıfır-xor yerleştirme oranı
$$\frac{m(L-s)}{L-s}$$
olur. Amaç fonksiyonu da bu iki oranın \(L\) ile ölçeklenmiş ortalamasıdır:
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
\(I=[A,B]\) ve \(J=[C,D]\) aynı Grundy değerini taşıyan iki aralık olsun. Sabit bir \(u\) için bir \(x\) değeri, ancak \(x\in I\) ve aynı anda \(u-x\in J\) ise \(m(u)\)'ya katkı yapar. Bu da
$$x\in I\cap [u-D,u-C]$$
demektir. Dolayısıyla bu çiftin katkısı örtüşme uzunluğudur:
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
\(u\) değiştikçe \(\lambda_{I,J}(u)\) parça doğrusal davranır: önce doğrusal artar, gerekirse sabit kalır, sonra doğrusal azalır. Eğimin değişebileceği tek noktalar uçların çakıştığı anlardır; yani
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
Eşit Grundy değerine sahip tüm aralık çiftlerinin bu trapez katkıları toplandığında,
$$m(u)=s_i u+c_i \qquad (u\in I_i)$$
şeklinde küresel bir parça doğrusal spline elde edilir. Farklı iki aralık, \((I,J)\) ve \((J,I)\) olarak iki sırada da önemlidir; bu yüzden iki kat ağırlık alır. Aynı aralığın kendisiyle oluşturduğu diyagonal çift ise bir kez sayılır.
\(m(u)\) parça doğrusal olduktan sonra, her iki kaydırılmış argümanın da sabit spline parçaları içinde kaldığı her \(L\) aralığında \(e(L)\) basit bir fonksiyona dönüşür. Eğer
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2$$
ise
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
\(e'(L)\) ile aynı köklere sahip bir ifade
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}$$
olur. Bu yüzden yerel maksimum ancak aralık uçlarında ya da bu ifadenin iç köklerinde bulunabilir. Böylece \([A,B]\) üzerindeki sürekli arama, sonlu sayıda tek boyutlu kök kontrolüne indirgenir.
Her \(u<1\) için, uzunluğu \(u\) olan bir segmente hiçbir kare sığmaz; dolayısıyla \(g(u)=0\). Sonuç olarak \(0\le u\le 1\) olduğunda \([0,u]\) üzerinde hemen her \(x\) için \(g(x)=g(u-x)=0\) olur ve
$$m(u)=u$$
elde edilir. Şimdi \(L=2\) alalım. O zaman
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
Kenar uzunluğu \(1\) için her yerleştirme, toplamı \(1\) olan iki alt segment bırakır; dolayısıyla ölçüsü \(0\) olan uç noktalar dışında her iki parça da \(1\)'den küçüktür ve xor her zaman \(0\) olur. Kenar uzunluğu \(\sqrt{2}\) için kalan toplam uzunluk zaten \(1\)'den küçüktür; burada da her yerleştirme xor \(0\) verir. Demek ki
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
Formülde yerine koyunca
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2$$
çıkar; bu da implementasyonların ilk doğrulama kontrolüyle aynıdır.
C++ ve Java implementasyonları bu türetimi doğrudan izler. Önce gerekli üst sınıra kadar tüm \(a+b\sqrt{2}\) kırılma noktaları üretilir, sıralanır ve ortaya çıkan aralıklar soldan sağa taranır. Her aralıkta orta noktadan erişilebilir xor kümesi hesaplanır, mex alınır ve Grundy değeri değişmiyorsa komşu aralıklar birleştirilir.
Daha sonra aralıklar Grundy değerlerine göre gruplanır ve \(m(u)\) için parça doğrusal spline oluşturulur. Eşit Grundy değerli her aralık çifti, eğimin değişebileceği dört olay noktası üretir; bu olaylar sıralandıktan sonra tek bir sweep ile bütün \(s_i u+c_i\) parçaları yeniden kurulur.
Son adımda, spline sınırlarının \(1\) ve \(\sqrt{2}\) kadar kaydırılmasıyla oluşan \(L\) kırılma noktaları hazırlanır. Her böyle aralıkta implementasyon uç noktaları değerlendirir, türev ifadesinde işaret değişimi arar ve iç kritik nokta varsa bisection uygular. Python implementasyonu yalnızca C++ çözücüsüne ince bir köprü görevi görür; C++ tarafı son değeri yazdırmadan önce \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\) ve \(f(10,20)=5.99374121\) gibi kontrol noktalarını da doğrular.
\(B\), arama sınırına kadar olan ham \(a+b\sqrt{2}\) kırılma noktalarının sayısı; \(S\) ise aynı komşu değerler birleştirildikten sonra kalan Grundy aralıklarının sayısı olsun. Ham kırılma noktalarını üretip sıralamak \(O(B\log B)\) zaman alır.
Parça sabit Grundy tablosunu kurmak en kötü durumda \(O(S^2)\)'dir; çünkü yeni bir aralık, erişilebilir xor değerlerini toplamak için daha önce oluşmuş aralıkların büyük bir bölümünü tarayabilir. Eşit Grundy aralık çiftlerinden \(m(u)\) fonksiyonunu üretmek de en kötü durumda kuadratiktir: \(k\) Grundy değerini taşıyan aralık sayısı \(n_k\) ise çift üretiminin maliyeti \(O\left(\sum_k n_k^2\right)\) olur; ardından aynı büyüklükte olay listesi logaritmik bir çarpanla sıralanır.
Son maksimum araması, türetilmiş \(L\) aralıklarının sayısına doğrusal ölçektedir; her aralıkta sabit sayıda değer hesabı ve sabit sayıda bisection iterasyonu yapılır. Bellek kullanımı \(O(S+E)\)'dir; burada \(E\), spline inşasındaki olay kayıtlarının sayısıdır.
Una posición es un segmento de longitud \(L\). Un movimiento legal elige un cuadrado de lado \(s\in\{1,\sqrt{2}\}\) y apoya su base sobre el segmento, de modo que el intervalo ocupado tiene longitud \(s\). Si el borde izquierdo está en \(x\), se elimina \([x,x+s]\) y quedan dos subjuegos independientes de longitudes \(x\) y \(L-s-x\).
Las implementaciones en C++, Python y Java estudian esto como un juego de Sprague-Grundy. Después maximizan la proporción media escalada de movimientos que dejan xor \(0\)
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
y calculan
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500).$$
Aquí \(m(u)\) mide la longitud total de las colocaciones que dividen el resto \(u\) en dos subposiciones con el mismo valor de Grundy. El problema se convierte así en un análisis continuo de juego imparcial seguido por una maximización en una sola variable.
La derivación tiene dos capas. Primero se calcula la función de Grundy \(g(L)\) para longitudes reales. Luego se construye una segunda función \(m(u)\) que cuenta los movimientos con xor nulo, y finalmente se maximiza la fórmula explícita de \(e(L)\).
Para \(0\le L<1\) no cabe ningún cuadrado, así que la posición es terminal y
$$g(L)=0.$$
Para valores mayores de \(L\), un cuadrado de lado \(s\in\{1,\sqrt{2}\}\) puede empezar en cualquier \(x\) con \(0\le x\le L-s\). Las dos partes restantes son independientes, por lo que el nimber del movimiento es
$$g(x)\oplus g(L-s-x).$$
Por tanto,
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$$
donde el segundo conjunto desaparece si \(L<\sqrt{2}\). Es la recurrencia estándar de Sprague-Grundy, pero con una longitud real como parámetro del juego.
Cada jugada elimina \(1\) o \(\sqrt{2}\) de longitud ocupada antes de partir el resto. Empezando en \(0\), la estructura combinatoria solo puede cambiar en sumas formadas con esos dos generadores:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
Como \(\sqrt{2}\) es irracional, pares distintos \((a,b)\) producen números reales distintos. Al ordenar esos valores, cualquier intervalo abierto entre dos puntos consecutivos tiene el mismo patrón de interacción con los intervalos anteriores desplazados por \(1\) y por \(\sqrt{2}\). Por ello, el conjunto de xor alcanzables permanece constante dentro de ese intervalo, y \(g(L)\) es constante por tramos.
Esa es la simplificación estructural que usan las implementaciones: en lugar de muestrear longitudes reales arbitrarias, almacenan intervalos fusionados donde un solo valor de Grundy vale en todo el tramo.
Fijemos un lado \(s\) y una longitud total \(L\). Una colocación en \(x\) es estratégicamente importante cuando deja xor \(0\), porque entonces el siguiente jugador recibe una \(P\)-posición. La condición es
$$g(x)\oplus g(L-s-x)=0,$$
equivalente a
$$g(x)=g(L-s-x).$$
Sea \(u=L-s\). La longitud total de tales colocaciones es
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$$
Como el intervalo legal de puntos iniciales tiene longitud \(u\), la fracción de colocaciones con xor cero para el lado \(s\) es
$$\frac{m(L-s)}{L-s}.$$
La función objetivo es exactamente el promedio de esas dos fracciones, escalado por \(L\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
Supongamos que \(I=[A,B]\) y \(J=[C,D]\) son dos intervalos con el mismo valor de Grundy. Para un \(u\) fijo, un punto \(x\) contribuye a \(m(u)\) si \(x\in I\) y además \(u-x\in J\). Eso equivale a
$$x\in I\cap [u-D,u-C].$$
Así, la contribución de ese par es la longitud de solapamiento
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
Cuando \(u\) varía, \(\lambda_{I,J}(u)\) es lineal a trozos: primero crece linealmente, quizá se mantiene constante y luego decrece linealmente. La pendiente solo puede cambiar cuando un extremo coincide con otro, es decir, en
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
Al sumar esas contribuciones trapezoidales sobre todos los pares de intervalos con el mismo Grundy, obtenemos una spline global lineal a trozos
$$m(u)=s_i u+c_i \qquad (u\in I_i).$$
Los intervalos distintos cuentan en ambos órdenes \((I,J)\) y \((J,I)\), por lo que reciben peso doble; un par diagonal solo cuenta una vez.
Una vez que \(m(u)\) es lineal a trozos, la función \(e(L)\) se vuelve elemental en cada intervalo donde ambos argumentos desplazados permanecen dentro de piezas fijas de la spline. Si
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$$
entonces
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
Una expresión con las mismas raíces que \(e'(L)\) es
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$$
Por tanto, todo máximo local debe aparecer en un extremo del intervalo o en una raíz interior de esa expresión. La búsqueda continua en \([A,B]\) se reduce a una colección finita de verificaciones unidimensionales.
Para todo \(u<1\), no cabe ningún cuadrado en un segmento de longitud \(u\), así que \(g(u)=0\). En consecuencia, si \(0\le u\le 1\), entonces \(g(x)=g(u-x)=0\) para casi todo \(x\in[0,u]\), y por tanto
$$m(u)=u.$$
Ahora fijemos \(L=2\). Entonces
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
Para el lado \(1\), toda colocación deja dos subsegmentos cuya longitud total es \(1\), así que ambos permanecen por debajo de \(1\) salvo en extremos de medida \(0\); el xor siempre es \(0\). Para el lado \(\sqrt{2}\), la longitud restante total ya es menor que \(1\), de modo que toda colocación también produce xor \(0\). Luego
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
Al sustituir en la fórmula se obtiene
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$$
exactamente el primer valor de validación usado por las implementaciones.
Las implementaciones en C++ y Java siguen la derivación de forma literal. Primero enumeran todos los puntos de quiebre \(a+b\sqrt{2}\) hasta el límite necesario, los ordenan y recorren los intervalos resultantes de izquierda a derecha. En cada intervalo evalúan el conjunto de xor alcanzables en un punto medio, calculan el mex y fusionan intervalos contiguos cuando el valor de Grundy no cambia.
Después agrupan esos intervalos por valor de Grundy y construyen la spline lineal a trozos para \(m(u)\). Cada par de intervalos con el mismo Grundy aporta cuatro posiciones de evento donde la pendiente puede cambiar; al ordenar esos eventos, un único barrido reconstruye todas las piezas lineales \(s_i u+c_i\).
Por último generan los puntos de quiebre en \(L\) que aparecen al desplazar los bordes de la spline en \(1\) y \(\sqrt{2}\). En cada intervalo así obtenido, la implementación evalúa los extremos, busca cambios de signo en la expresión de la derivada y usa bisección cuando existe un punto crítico interior. La implementación en Python es solo un envoltorio fino sobre el solucionador en C++, mientras que la versión en C++ también verifica puntos de control como \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\) y \(f(10,20)=5.99374121\).
Sea \(B\) el número de puntos de quiebre brutos \(a+b\sqrt{2}\) hasta el límite de búsqueda, y sea \(S\) el número de intervalos de Grundy fusionados tras unir vecinos con el mismo valor. Generar y ordenar los puntos de quiebre cuesta \(O(B\log B)\).
Construir la tabla de Grundy constante por tramos es \(O(S^2)\) en el peor caso, porque cada intervalo nuevo puede recorrer una porción grande de los intervalos ya construidos para reunir todos los xor alcanzables. Construir \(m(u)\) a partir de pares de intervalos con el mismo Grundy también es cuadrático en el peor caso: si \(n_k\) intervalos tienen valor de Grundy \(k\), el coste de generar pares es \(O\left(\sum_k n_k^2\right)\), seguido por una ordenación de eventos del mismo orden salvo por un factor logarítmico.
La pasada final de maximización es lineal en el número de intervalos inducidos en \(L\), con solo evaluaciones de tiempo constante y un número fijo de iteraciones de bisección por intervalo. El uso de memoria es \(O(S+E)\), donde \(E\) es el número de registros de evento utilizados para construir la spline.
一个局面是一条长度为 \(L\) 的线段。一次合法操作选择边长 \(s\in\{1,\sqrt{2}\}\) 的正方形，并把它的底边放在线段上，因此被占据的投影区间长度就是 \(s\)。如果左端点是 \(x\)，那么被移走的是 \([x,x+s]\)，剩下两个互不干扰的子局面，长度分别为 \(x\) 和 \(L-s-x\)。
C++、Python 和 Java 实现都把它看成一个 Sprague-Grundy 博弈。随后它们最大化“留下 xor 为 \(0\) 的走法比例”的缩放平均值
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
并计算
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500)$$
这里的 \(m(u)\) 表示：当剩余总长度为 \(u\) 时，有多少长度的放置方式会把局面分成两个 Grundy 值相同的子局面。于是整道题就变成了“连续长度上的 impartial game 分析”加上“单变量极大值搜索”。
推导分成两层。第一层先求实数长度上的 Grundy 函数 \(g(L)\)。第二层再由 \(g\) 构造一个测度函数 \(m(u)\)，专门统计哪些落子会把 xor 变成 \(0\)。最后把得到的显式公式 \(e(L)\) 在目标区间上取最大值。
当 \(0\le L<1\) 时，没有任何正方形能够放下，因此这是终止局面，满足
$$g(L)=0$$
当 \(L\) 更大时，边长 \(s\in\{1,\sqrt{2}\}\) 的正方形可以从任意 \(x\) 开始放置，只要 \(0\le x\le L-s\)。删除这段以后，左右两边是两个独立子局面，所以该走法的 nimber 为
$$g(x)\oplus g(L-s-x)$$
因此有
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr)$$
其中第二个集合只在 \(L\ge\sqrt{2}\) 时存在。这就是标准的 Sprague-Grundy 递推，只不过这里的状态参数不是整数，而是实数长度。
每一步操作在分裂剩余部分之前，都会从总长度中减去 \(1\) 或 \(\sqrt{2}\)。从 \(0\) 出发，局面的组合结构只有可能在由这两个生成元组成的和上发生变化：
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}$$
由于 \(\sqrt{2}\) 是无理数，不同的 \((a,b)\) 会得到不同的实数值。把这些值排序之后，相邻两个断点之间的任意开区间，与所有更早区间在平移 \(1\) 和平移 \(\sqrt{2}\) 后的相互关系都不会改变。所以该开区间内“可达 xor 值的集合”保持不变，也就是说 \(g(L)\) 在每一段上都是常数。
这正是实现所利用的核心结构：不去枚举任意实数长度，而是维护一张“分段常值的 Grundy 区间表”，把相邻且 Grundy 值相同的部分直接合并。
现在固定一种边长 \(s\) 和总长度 \(L\)。如果在位置 \(x\) 放置正方形后留下的 xor 等于 \(0\)，那么下一位玩家就会面对一个 \(P\)-position，这种落子在策略上最关键。条件是
$$g(x)\oplus g(L-s-x)=0$$
等价于
$$g(x)=g(L-s-x)$$
令 \(u=L-s\)。满足条件的所有 \(x\) 的总长度定义为
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right)$$
因为合法左端点的区间总长度就是 \(u\)，所以对于边长 \(s\)，留下零 xor 的走法所占比例为
$$\frac{m(L-s)}{L-s}$$
实现里要最大化的目标函数，正是这两个比例的平均值再乘以 \(L\)：
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right)$$
设 \(I=[A,B]\) 和 \(J=[C,D]\) 是两个 Grundy 值相同的区间。对于固定的 \(u\)，一个点 \(x\) 会对 \(m(u)\) 产生贡献，当且仅当 \(x\in I\) 且 \(u-x\in J\)。这等价于
$$x\in I\cap [u-D,u-C]$$
因此这个区间对 \(m(u)\) 的贡献就是重叠长度
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right)$$
当 \(u\) 变化时，\(\lambda_{I,J}(u)\) 是一条分段线性函数：先线性增长，可能出现平台，然后再线性下降。只有在端点相遇时斜率才会改变，也就是
$$u=A+C,\quad A+D,\quad B+C,\quad B+D$$
把所有“Grundy 值相同”的区间对的这类梯形贡献累加起来，就能得到一条全局分段线性样条
$$m(u)=s_i u+c_i \qquad (u\in I_i)$$
如果 \(I\neq J\)，那么有序对 \((I,J)\) 和 \((J,I)\) 都要计入，所以权重是两倍；若是同一段与自身配对，则只计一次。
一旦 \(m(u)\) 已经是分段线性的，\(e(L)\) 在每个区间上就会变成初等函数，只要 \(L-1\) 和 \(L-\sqrt{2}\) 这两个平移后的参数分别落在固定的样条段内。若
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2$$
则
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right)$$
与 \(e'(L)\) 拥有完全相同零点的表达式是
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}$$
所以每一个局部最大值，要么出现在区间端点，要么出现在这个表达式的内部根上。原本的连续搜索问题因此被压缩成有限多个一维求根检查。
对所有 \(u<1\)，长度为 \(u\) 的线段上都放不下任何正方形，所以 \(g(u)=0\)。于是只要 \(0\le u\le 1\)，对几乎所有 \(x\in[0,u]\) 都有 \(g(x)=g(u-x)=0\)，从而
$$m(u)=u$$
现在取 \(L=2\)。此时
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1$$
对于边长 \(1\) 的正方形，每一种放置都会留下总长度为 \(1\) 的两段，因此除了测度为 \(0\) 的端点之外，两边都严格小于 \(1\)，xor 始终为 \(0\)。对于边长 \(\sqrt{2}\) 的正方形，剩余总长度已经小于 \(1\)，于是每一种放置同样都得到 xor \(0\)。所以
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}$$
代回公式可得
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2$$
这正好对应实现中最先检查的验证值。
C++ 和 Java 实现严格按照上面的数学结构推进。首先，它们枚举所需上界以内的所有 \(a+b\sqrt{2}\) 断点，排序后从左到右扫描这些断点之间的区间。对每一段，先在中点处收集所有可达 xor 值，再取 mex，最后把 Grundy 值相同的相邻区间合并。
接着，这些区间会按 Grundy 值重新分组，并进一步构造 \(m(u)\) 的分段线性样条。每一对同 Grundy 区间都会产生四个“斜率可能变化的事件位置”；把事件排序后，只要做一次扫描，就能重建出所有 \(s_i u+c_i\) 线性片段。
最后，再把样条边界分别平移 \(1\) 和 \(\sqrt{2}\)，得到 \(L\) 方向上的搜索区间。实现会在每段中检查端点值，查看导数表达式是否发生符号变化，并在存在内部临界点时用二分法定位。Python 实现本身只是对 C++ 求解器的一层轻量包装，而 C++ 版本在输出最终答案前还会验证若干检查点，包括 \(e(2)=2\)、\(e(4)=1.11974851\)、\(f(2,10)=2.61969775\) 和 \(f(10,20)=5.99374121\)。
设 \(B\) 是搜索上界以内原始断点 \(a+b\sqrt{2}\) 的数量，\(S\) 是把相邻同值区间合并之后得到的 Grundy 区间数。生成并排序这些原始断点需要 \(O(B\log B)\) 时间。
构造分段常值的 Grundy 表在最坏情况下是 \(O(S^2)\)，因为每加入一段新区间，都可能要扫描先前已经建立的大量区间来收集可达 xor 值。由同 Grundy 区间对构造 \(m(u)\) 在最坏情况下也呈二次复杂度：如果 Grundy 值为 \(k\) 的区间数是 \(n_k\)，那么配对成本为 \(O\left(\sum_k n_k^2\right)\)，随后事件排序再乘一个对数因子。
最终的极值搜索对 \(L\) 的诱导区间数是线性的；每一段只需要常数次函数求值以及固定次数的二分迭代。内存复杂度是 \(O(S+E)\)，其中 \(E\) 表示样条构造过程中生成的事件记录数。
Позиция представляет собой отрезок длины \(L\). Разрешенный ход выбирает квадрат со стороной \(s\in\{1,\sqrt{2}\}\) и размещает его основание на отрезке, так что занятый промежуток имеет длину \(s\). Если левая граница находится в точке \(x\), то удаляется \([x,x+s]\), а остаются две независимые подпозиции длины \(x\) и \(L-s-x\).
Реализации на C++, Python и Java рассматривают это как игру Шпрага-Гранди. Затем они максимизируют масштабированную среднюю долю ходов, оставляющих xor равным \(0\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
и вычисляют
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500).$$
Здесь \(m(u)\) обозначает суммарную длину всех размещений, которые разбивают остаток длины \(u\) на две подпозиции с одинаковым значением Гранди. Значит, задача сводится к непрерывному анализу impartial game и последующему поиску максимума функции одной переменной.
Вывод состоит из двух уровней. Сначала строится функция Гранди \(g(L)\) для вещественной длины. Затем из нее выводится функция \(m(u)\), считающая ходы с нулевым xor, и уже после этого максимизируется явная формула для \(e(L)\).
При \(0\le L<1\) ни один квадрат не помещается, поэтому позиция терминальная и
$$g(L)=0.$$
Для больших \(L\) квадрат со стороной \(s\in\{1,\sqrt{2}\}\) можно поставить в любую точку \(x\), где \(0\le x\le L-s\). Оставшиеся части независимы, поэтому nimber такого хода равен
$$g(x)\oplus g(L-s-x).$$
Следовательно,
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$$
где второе множество отсутствует, если \(L<\sqrt{2}\). Это обычная рекурсия Шпрага-Гранди, только параметром состояния теперь служит вещественная длина.
Каждый ход вычитает из общей занятой длины либо \(1\), либо \(\sqrt{2}\), прежде чем остаток распадется на две части. Начиная с \(0\), комбинаторная структура может меняться только в точках, представимых как сумма этих двух генераторов:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
Поскольку \(\sqrt{2}\) иррационально, разные пары \((a,b)\) дают разные вещественные числа. Если упорядочить эти значения, то на каждом открытом промежутке между соседними точками разбиения сохраняется один и тот же шаблон взаимодействия с более ранними промежутками, сдвинутыми на \(1\) и на \(\sqrt{2}\). Поэтому множество достижимых xor-значений на таком промежутке постоянно, а \(g(L)\) оказывается кусочно постоянной функцией.
Именно этим пользуются реализации: вместо перебора произвольных вещественных длин они хранят объединенные интервалы, на каждом из которых действует одно и то же значение Гранди.
Зафиксируем длину стороны \(s\) и общую длину \(L\). Размещение в точке \(x\) стратегически важно тогда, когда после него xor становится равным \(0\), потому что следующий игрок получает \(P\)-позицию. Условие имеет вид
$$g(x)\oplus g(L-s-x)=0,$$
то есть эквивалентно
$$g(x)=g(L-s-x).$$
Положим \(u=L-s\). Тогда суммарная длина всех таких размещений равна
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$$
Так как допустимый интервал для левого края имеет длину \(u\), доля нулевых xor-размещений для стороны \(s\) равна
$$\frac{m(L-s)}{L-s}.$$
Целевая функция как раз и есть среднее значение этих двух долей, умноженное на \(L\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
Пусть \(I=[A,B]\) и \(J=[C,D]\) - два интервала с одинаковым значением Гранди. Для фиксированного \(u\) точка \(x\) вносит вклад в \(m(u)\) тогда и только тогда, когда \(x\in I\) и одновременно \(u-x\in J\). Это эквивалентно условию
$$x\in I\cap [u-D,u-C].$$
Значит, вклад этой пары интервалов равен длине пересечения
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
При изменении \(u\) функция \(\lambda_{I,J}(u)\) кусочно линейна: сначала линейно растет, затем может оставаться постоянной, а потом линейно убывает. Ее наклон меняется только тогда, когда совпадают концы интервалов, то есть в точках
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
Если суммировать такие трапецеидальные вклады по всем парам интервалов с одинаковым значением Гранди, получится глобальный кусочно-линейный сплайн
$$m(u)=s_i u+c_i \qquad (u\in I_i).$$
Разные интервалы учитываются в двух порядках, \((I,J)\) и \((J,I)\), поэтому получают двойной вес; диагональная пара учитывается один раз.
После того как \(m(u)\) стала кусочно-линейной, функция \(e(L)\) на каждом промежутке становится элементарной, если оба сдвинутых аргумента лежат в фиксированных кусках сплайна. Если
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$$
то
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
Выражение с теми же нулями, что и у \(e'(L)\), имеет вид
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$$
Значит, локальный максимум может находиться только на границе интервала или во внутреннем корне этого выражения. Тем самым непрерывный поиск по \([A,B]\) превращается в конечное число одномерных проверок корней.
Для любого \(u<1\) на отрезок длины \(u\) не помещается ни один квадрат, поэтому \(g(u)=0\). Следовательно, при \(0\le u\le 1\) почти для всех \(x\in[0,u]\) выполнено \(g(x)=g(u-x)=0\), и значит
$$m(u)=u.$$
Теперь возьмем \(L=2\). Тогда
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
Для стороны \(1\) любое размещение оставляет два подотрезка суммарной длины \(1\), значит, за исключением концов меры \(0\), оба они короче \(1\), и xor всегда равен \(0\). Для стороны \(\sqrt{2}\) оставшаяся суммарная длина уже меньше \(1\), поэтому там тоже любой ход дает xor \(0\). Отсюда
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
Подстановка в формулу дает
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$$
что в точности совпадает с первой проверкой в реализациях.
Реализации на C++ и Java буквально следуют приведенному выводу. Сначала они перечисляют все точки разбиения \(a+b\sqrt{2}\) до нужного предела, сортируют их и проходят по получившимся интервалам слева направо. На каждом интервале вычисляется множество достижимых xor-значений в средней точке, затем берется mex, а соседние интервалы с одинаковым значением Гранди сливаются.
Затем интервалы группируются по значению Гранди, и из них строится кусочно-линейный сплайн для \(m(u)\). Каждая пара интервалов с одинаковым значением Гранди порождает четыре позиции событий, в которых может измениться наклон; после сортировки этих событий один проход восстанавливает все линейные куски \(s_i u+c_i\).
Наконец формируются точки разбиения по \(L\), возникающие из-за сдвига границ сплайна на \(1\) и \(\sqrt{2}\). На каждом таком промежутке реализация проверяет значения на концах, ищет смену знака в выражении для производной и при наличии внутренней критической точки применяет бисекцию. Python-реализация представляет собой только тонкую оболочку вокруг C++-решателя, а версия на C++ дополнительно проверяет контрольные значения \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\) и \(f(10,20)=5.99374121\).
Обозначим через \(B\) количество исходных точек разбиения \(a+b\sqrt{2}\) до верхней границы поиска, а через \(S\) - число объединенных интервалов Гранди после склейки соседних одинаковых значений. Генерация и сортировка исходных точек стоят \(O(B\log B)\).
Построение кусочно-постоянной таблицы Гранди в худшем случае занимает \(O(S^2)\), поскольку каждый новый интервал может просматривать значительную часть уже построенных интервалов, чтобы собрать все достижимые xor-значения. Построение \(m(u)\) по парам интервалов с одинаковым значением Гранди тоже квадратично в худшем случае: если значение \(k\) встречается на \(n_k\) интервалах, то стоимость генерации пар равна \(O\left(\sum_k n_k^2\right)\), после чего идет сортировка событий того же порядка с логарифмическим множителем.
Последний проход по поиску максимума линеен по числу индуцированных интервалов по \(L\); на каждый интервал приходится лишь константное число вычислений и фиксированное число шагов бисекции. Память имеет порядок \(O(S+E)\), где \(E\) обозначает число событийных записей при построении сплайна.
الوضعية هي قطعة مستقيمة طولها \(L\). النقلة القانونية تختار مربعًا طول ضلعه \(s\in\{1,\sqrt{2}\}\) وتضع قاعدته على القطعة، ولذلك يكون طول الجزء المشغول هو \(s\). إذا كانت الحافة اليسرى عند \(x\)، فإن الجزء \([x,x+s]\) يُزال، وتبقى لعبتان مستقلتان بطولي \(x\) و \(L-s-x\).
تعامل تطبيقات C++ وPython وJava هذه البنية كلعبة Sprague-Grundy. بعد ذلك تبحث عن أكبر قيمة لمتوسط النسبة الموزونة للحركات التي تترك xor مساويًا للصفر:
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$$
ثم تحسب
$$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500).$$
هنا ترمز \(m(u)\) إلى الطول الكلي لجميع المواضع التي تقسّم الباقي ذي الطول \(u\) إلى وضعيتين فرعيتين لهما قيمة Grundy نفسها. وهكذا تتحول المسألة إلى تحليل لعبة impartial على مجال مستمر، ثم إلى مسألة تعظيم في متغير واحد.
الاشتقاق له طبقتان. أولًا نحسب دالة Grundy وهي \(g(L)\) عندما يكون الطول عددًا حقيقيًا. ثم نبني من هذه الدالة تابعًا ثانيًا هو \(m(u)\) يقيس الحركات التي تجعل xor يساوي الصفر، وبعد ذلك نعظّم الصيغة الصريحة لـ \(e(L)\).
إذا كان \(0\le L<1\)، فلا يوجد أي مربع يمكن وضعه، ولذلك تكون الوضعية نهائية ويكون
$$g(L)=0.$$
أما عندما يكون \(L\) أكبر، فإن مربعًا بطول ضلع \(s\in\{1,\sqrt{2}\}\) يمكن أن يبدأ من أي \(x\) يحقق \(0\le x\le L-s\). والجزآن المتبقيان بعد الإزالة مستقلان، ولذلك تكون قيمة nim لهذه النقلة
$$g(x)\oplus g(L-s-x).$$
إذن
$$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$$
مع حذف المجموعة الثانية إذا كان \(L<\sqrt{2}\). هذه هي علاقة Sprague-Grundy المعتادة، لكن متغير الحالة هنا طول حقيقي بدلًا من حجم صحيح.
كل نقلة تطرح من الطول المشغول إما \(1\) أو \(\sqrt{2}\) قبل أن يُقسَّم الباقي. انطلاقًا من \(0\)، لا يمكن أن تتغير البنية التوافقية إلا عند مجاميع مكوّنة من هذين المولّدين:
$$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$$
وبما أن \(\sqrt{2}\) عدد غير نسبي، فإن الأزواج المختلفة \((a,b)\) تعطي أعدادًا حقيقية مختلفة. وبعد ترتيب هذه القيم، فإن أي فترة مفتوحة بين نقطتي انكسار متتاليتين تمتلك نمط التفاعل نفسه مع كل الفترات الأقدم بعد إزاحتها بمقدار \(1\) وبمقدار \(\sqrt{2}\). لذلك تبقى مجموعة قيم xor الممكنة ثابتة على طول هذه الفترة، أي إن \(g(L)\) دالة ثابتة على مقاطع.
هذه هي البساطة البنيوية التي تعتمد عليها التطبيقات: بدلًا من التعامل مع كل طول حقيقي على حدة، تُخزَّن فترات مدمجة تحمل قيمة Grundy واحدة على كامل المقطع.
لنثبت طول ضلع \(s\) وطول القطعة \(L\). يكون الوضع عند الموضع \(x\) مهمًا استراتيجيًا إذا ترك xor مساويًا للصفر، لأن اللاعب التالي عندها يستلم \(P\)-position. الشرط هو
$$g(x)\oplus g(L-s-x)=0,$$
وهو مكافئ لـ
$$g(x)=g(L-s-x).$$
ضع \(u=L-s\). عندئذ يكون الطول الكلي لجميع هذه المواضع
$$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$$
ولأن المجال القانوني للحافة اليسرى طوله \(u\)، فإن نسبة المواضع التي تعطي xor صفريًا للمربع ذي الضلع \(s\) هي
$$\frac{m(L-s)}{L-s}.$$
ودالة الهدف هي بالضبط متوسط هاتين النسبتين بعد ضربه في \(L\):
$$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$$
افترض أن \(I=[A,B]\) و \(J=[C,D]\) فترتان لهما قيمة Grundy نفسها. من أجل \(u\) ثابت، يساهم عدد \(x\) في \(m(u)\) إذا وفقط إذا كان \(x\in I\) و \(u-x\in J\). وهذا يكافئ
$$x\in I\cap [u-D,u-C].$$
إذن مساهمة هذا الزوج من الفترات هي طول التقاطع
$$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$$
وعندما يتغير \(u\)، تكون \(\lambda_{I,J}(u)\) دالة خطية على مقاطع: تزداد خطيًا، وقد تستقر فترة قصيرة، ثم تنخفض خطيًا. ولا يتغير ميلها إلا عندما يلتقي طرف بطرف، أي عند القيم
$$u=A+C,\quad A+D,\quad B+C,\quad B+D.$$
وبجمع هذه المساهمات شبه المنحرفة على جميع أزواج الفترات ذات قيمة Grundy نفسها نحصل على spline خطية على مقاطع:
$$m(u)=s_i u+c_i \qquad (u\in I_i).$$
إذا كانت الفترتان مختلفتين، فكل من الترتيبين \((I,J)\) و \((J,I)\) مهم، ولذلك يُعطى الزوج وزنًا مضاعفًا. أما إذا كانت الفترتان متماثلتين، فيُحسب الزوج مرة واحدة فقط.
بعد أن تصبح \(m(u)\) خطية على مقاطع، فإن \(e(L)\) تصبح دالة أولية على كل فترة يبقى فيها كل من \(L-1\) و \(L-\sqrt{2}\) داخل قطعتين ثابتتين من الـ spline. فإذا كان
$$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$$
فإن
$$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$$
وتعبير يملك الجذور نفسها التي تملكها \(e'(L)\) هو
$$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$$
وبذلك لا يمكن أن يظهر أي عظمى محلية إلا عند طرف الفترة أو عند جذر داخلي لهذا التعبير. وبذلك تتحول عملية البحث المستمرة على \([A,B]\) إلى عدد منتهٍ من اختبارات الجذور أحادية البعد.
لكل \(u<1\)، لا يمكن وضع أي مربع على قطعة طولها \(u\)، وبالتالي \(g(u)=0\). ومن ثم إذا كان \(0\le u\le 1\)، فإن \(g(x)=g(u-x)=0\) تقريبًا لكل \(x\in[0,u]\)، ولذلك
$$m(u)=u.$$
خذ الآن \(L=2\). عندئذ
$$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$$
بالنسبة إلى الضلع \(1\)، فإن كل تموضع يترك قطعتين مجموع طولهما \(1\)، وبالتالي تبقيان أصغر من \(1\) باستثناء أطراف ذات قياس صفري؛ لذلك يكون xor دائمًا مساويًا للصفر. وبالنسبة إلى الضلع \(\sqrt{2}\)، فإن الطول الكلي المتبقي أصغر أصلًا من \(1\)، لذا فإن كل تموضع يعطي أيضًا xor صفريًا. إذن
$$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$$
وبالتعويض في الصيغة نحصل على
$$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$$
وهو تمامًا أول فحص تحقق تستخدمه التطبيقات.
يتبع تنفيذا C++ وJava هذا الاشتقاق خطوة بخطوة. في البداية يجريان تعدادًا لكل نقاط الانكسار \(a+b\sqrt{2}\) حتى الحد المطلوب، ثم يرتبانها ويمران على الفترات الناتجة من اليسار إلى اليمين. وفي كل فترة تُحسب مجموعة قيم xor الممكنة عند نقطة وسطية، ثم يؤخذ mex، وتُدمج الفترات المتجاورة إذا بقيت قيمة Grundy ثابتة.
بعد ذلك تُجمع الفترات بحسب قيمة Grundy، وتُبنى spline الخطية على مقاطع للدالة \(m(u)\). كل زوج من الفترات المتساوية في قيمة Grundy يولّد أربع نقاط أحداث يمكن أن يتغير عندها الميل؛ وبعد ترتيب هذه الأحداث يكفي مسح واحد لإعادة بناء كل قطعة خطية من الشكل \(s_i u+c_i\).
أخيرًا تُنشأ نقاط الانكسار في متغير \(L\) الناتجة عن إزاحة حدود الـ spline بمقدار \(1\) وبمقدار \(\sqrt{2}\). وعلى كل فترة من هذه الفترات، يفحص التنفيذ القيم عند النهايات، ويبحث عن تغير إشارة في تعبير المشتقة، ويستخدم طريقة التنصيف عند وجود نقطة حرجة داخلية. أما تنفيذ Python فهو مجرد غلاف خفيف حول محلل C++، في حين يتحقق تنفيذ C++ أيضًا من قيم مرجعية مثل \(e(2)=2\) و \(e(4)=1.11974851\) و \(f(2,10)=2.61969775\) و \(f(10,20)=5.99374121\) قبل طباعة النتيجة النهائية.
لنرمز بـ \(B\) إلى عدد نقاط الانكسار الخام \(a+b\sqrt{2}\) حتى حد البحث، وبـ \(S\) إلى عدد فترات Grundy المدمجة بعد جمع الجيران ذوي القيمة نفسها. توليد نقاط الانكسار الخام وترتيبها يكلف \(O(B\log B)\).
بناء جدول Grundy الثابت على مقاطع يكلف في أسوأ الأحوال \(O(S^2)\)، لأن كل فترة جديدة قد تضطر إلى فحص جزء كبير من الفترات السابقة لجمع كل قيم xor الممكنة. كما أن بناء \(m(u)\) من أزواج الفترات المتساوية في قيمة Grundy تربيعي أيضًا في أسوأ حالة: فإذا كان عدد الفترات ذات القيمة \(k\) هو \(n_k\)، فإن تكلفة إنشاء الأزواج هي \(O\left(\sum_k n_k^2\right)\)، ثم يأتي بعد ذلك ترتيب الأحداث من الرتبة نفسها مع عامل لوغاريتمي إضافي.
أما المرور الأخير للبحث عن العظمى فهو خطي في عدد الفترات المستحثة في \(L\)، مع عدد ثابت من تقييمات الدوال وعدد ثابت من خطوات التنصيف لكل فترة. واستهلاك الذاكرة هو \(O(S+E)\)، حيث \(E\) هو عدد سجلات الأحداث المستخدمة أثناء بناء الـ spline.