Start with a unit rectangle. In each of the \(ab\) rounds, Alex partitions the current rectangle into an \(a\times b\) grid; cuts may coincide, so some strips may have zero width or height. Bianca then chooses one cell label that has not been used before, and play continues inside that chosen cell. Alex wants the final area to be as large as possible, Bianca wants it as small as possible, and the common value under optimal play is denoted by \(S(a,b)\).
The C++, Python, and Java implementations do not search a minimax tree explicitly. Instead they use a closed formula for \(S(a,b)\) and then evaluate it numerically for \((a,b)=(5,8)\).
The decisive observation is that the geometry separates cleanly into a horizontal game and a vertical game. Once those one-dimensional subgames are solved, the full rectangle value follows immediately.
In round \(t\), let the column widths be \(x_1^{(t)},\dots,x_a^{(t)}\) with
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
and let the row heights be \(y_1^{(t)},\dots,y_b^{(t)}\) with
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
If Bianca chooses the cell in column \(i_t\) and row \(j_t\), then that round multiplies the remaining area by
$$x_{i_t}^{(t)}y_{j_t}^{(t)}.$$
After all \(ab\) rounds, the final area is
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
So the two-dimensional game factors into a horizontal contribution times a vertical contribution.
View the \(ab\) cell labels as the pairs \((i,j)\) with \(1\le i\le a\) and \(1\le j\le b\). Because the game lasts exactly \(ab\) rounds and Bianca may never reuse a label, every pair is used exactly once by the end.
That fixes the total multiplicities automatically:
$$\text{each column index }i\text{ appears exactly }b\text{ times},$$
$$\text{each row index }j\text{ appears exactly }a\text{ times}.$$
Hence the horizontal part is a one-dimensional interval game with \(a\) labels, each required \(b\) times, and the vertical part is the same construction with \(b\) labels, each required \(a\) times.
Let
$$T_n(r_1,\dots,r_n)$$
denote the optimal value of the interval version when label \(i\) still has to be chosen \(r_i\) more times. Write
$$R=r_1+\cdots+r_n.$$
If Alex splits the current interval into lengths \(x_1,\dots,x_n\) with \(x_i\ge 0\) and \(\sum x_i=1\), then Bianca chooses any label with \(r_i>0\). The continuation value is therefore
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
So the minimax recurrence is
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
At an optimal split, every currently available choice must lead to the same value. Otherwise Alex could move a little length away from a larger branch and toward a smaller branch, improving the minimum. Thus for every active \(i\),
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
for one common constant \(\lambda\). Therefore
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
Summing over all active labels gives
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
hence
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
The recurrence is solved by
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
Indeed, substituting this expression gives
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
so
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
whose reciprocal is exactly \(\frac{\prod r_i!}{R!}\). The corresponding optimal split is especially simple:
$$x_i=\frac{r_i}{R}.$$
So each active strip gets length proportional to the number of times it still must be chosen, while exhausted labels can receive zero width because cuts are allowed to coincide.
At the start of the horizontal game, there are \(a\) labels and each must be used \(b\) times, hence
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
At the start of the vertical game, there are \(b\) labels and each must be used \(a\) times, hence
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
Multiplying the independent factors yields
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
This is exactly the formula used by the implementations.
For \((a,b)=(2,2)\), the one-dimensional value is
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
so
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
For \((a,b)=(2,3)\), the two factors are
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
and therefore
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
which matches the standard checkpoints.
The C++, Python, and Java implementations all use the closed formula above instead of traversing the full game tree. They evaluate
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
This avoids constructing enormous factorials directly. In C++ and Python, \(\log_{10}(n!)\) is obtained through the identity \(\log(n!)=\log\Gamma(n+1)\); the Java implementation uses the equivalent sum \(\sum_{k=1}^{n}\log_{10} k\).
After computing \(\log_{10}S\), the implementation writes
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
so that
$$S=10^{\theta}\times 10^{e}.$$
The mantissa \(10^{\theta}\) is then rounded to exactly 10 digits after the decimal point. A final carry check is needed because rounding can turn a mantissa such as \(9.99999999996\) into \(10.0000000000\), which must be renormalized as \(1.0000000000\times 10^{e+1}\). The C++ implementation also verifies the small cases \(S(2,2)\) and \(S(2,3)\) before printing the result for \((5,8)\).
For the fixed Project Euler target input, the computation is effectively \(O(1)\) time and \(O(1)\) memory in all three languages. More generally, the mathematical formula itself has constant size once the needed log-factorials are available. The C++ and Python versions obtain them with a constant number of library calls, while the Java version computes them by summing decimal logarithms up to \(ab\), still using only \(O(1)\) extra space.
Ausgangspunkt ist ein Einheitsrechteck. In jeder der \(ab\) Runden zerlegt Alex das aktuelle Rechteck in ein \(a\times b\)-Gitter; Schnitte dürfen zusammenfallen, also sind auch Streifen mit Breite oder Höhe \(0\) erlaubt. Danach wählt Bianca ein Zelllabel, das zuvor noch nicht benutzt wurde, und das Spiel wird innerhalb dieser Zelle fortgesetzt. Alex möchte die Endfläche maximieren, Bianca möchte sie minimieren, und der gemeinsame Spielwert heißt \(S(a,b)\).
Die Implementierungen in C++, Python und Java durchsuchen keinen expliziten Minimax-Baum. Stattdessen verwenden sie eine geschlossene Formel für \(S(a,b)\) und werten diese dann numerisch für \((a,b)=(5,8)\) aus.
Der entscheidende Punkt ist, dass sich die Geometrie sauber in ein horizontales und ein vertikales Teilspiel zerlegt. Sobald diese eindimensionalen Spiele gelöst sind, ergibt sich der Rechteckwert sofort.
In Runde \(t\) seien die Spaltenbreiten \(x_1^{(t)},\dots,x_a^{(t)}\) mit
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
und die Zeilenhöhen \(y_1^{(t)},\dots,y_b^{(t)}\) mit
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
Wählt Bianca die Zelle in Spalte \(i_t\) und Zeile \(j_t\), dann wird die verbleibende Fläche in dieser Runde mit
$$x_{i_t}^{(t)}y_{j_t}^{(t)}$$
multipliziert. Nach allen \(ab\) Runden ist die Endfläche also
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
Das zweidimensionale Spiel faktorisiert damit in einen horizontalen und einen vertikalen Beitrag.
Man kann die \(ab\) Zelllabels als Paare \((i,j)\) mit \(1\le i\le a\) und \(1\le j\le b\) auffassen. Da das Spiel genau \(ab\) Runden dauert und Bianca kein Label wiederverwenden darf, wird jedes Paar am Ende genau einmal benutzt.
Damit sind die Gesamthäufigkeiten fest:
$$\text{jeder Spaltenindex }i\text{ erscheint genau }b\text{-mal},$$
$$\text{jeder Zeilenindex }j\text{ erscheint genau }a\text{-mal}.$$
Der horizontale Anteil ist also ein eindimensionales Intervallspiel mit \(a\) Labels, die jeweils \(b\)-mal gewählt werden müssen, und der vertikale Anteil ist dieselbe Konstruktion mit \(b\) Labels, die jeweils \(a\)-mal gebraucht werden.
Sei
$$T_n(r_1,\dots,r_n)$$
der optimale Wert der Intervallversion, wenn Label \(i\) noch genau \(r_i\) Mal ausgewählt werden muss. Setze
$$R=r_1+\cdots+r_n.$$
Teilt Alex das aktuelle Intervall in Längen \(x_1,\dots,x_n\) mit \(x_i\ge 0\) und \(\sum x_i=1\), dann wählt Bianca irgendein Label mit \(r_i>0\). Der Fortsetzungswert lautet dann
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
Somit ergibt sich die Minimax-Rekursion
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
In einer optimalen Zerlegung müssen alle aktuell verfügbaren Entscheidungen denselben Wert liefern. Sonst könnte Alex ein wenig Länge von einem größeren Ast zu einem kleineren verschieben und damit das Minimum verbessern. Also gilt für jedes aktive \(i\)
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
mit einer gemeinsamen Konstante \(\lambda\). Damit folgt
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
Summation über alle aktiven Labels liefert
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
also
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
Die Rekursion wird gelöst durch
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
Setzt man diesen Kandidaten ein, so erhält man
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
und damit
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
dessen Kehrwert genau \(\frac{\prod r_i!}{R!}\) ist. Die optimale Zerlegung ist dadurch besonders einfach:
$$x_i=\frac{r_i}{R}.$$
Jeder aktive Streifen bekommt also eine Länge proportional dazu, wie oft er noch gebraucht wird; ausgeschöpfte Labels dürfen Breite \(0\) erhalten, weil Schnitte zusammenfallen dürfen.
Zu Beginn des horizontalen Spiels gibt es \(a\) Labels, die jeweils \(b\)-mal gebraucht werden. Also
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
Zu Beginn des vertikalen Spiels gibt es \(b\) Labels, die jeweils \(a\)-mal gebraucht werden. Also
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
Multiplikation der beiden unabhängigen Faktoren ergibt
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
Genau diese Formel wird von den Implementierungen benutzt.
Für \((a,b)=(2,2)\) ist der eindimensionale Wert
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
also
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
Für \((a,b)=(2,3)\) lauten die beiden Faktoren
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
und damit
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
was mit den bekannten Kontrollwerten übereinstimmt.
Die Implementierungen in C++, Python und Java verwenden alle die geschlossene Formel oben, statt den vollständigen Spielbaum zu durchsuchen. Sie berechnen
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
Dadurch müssen riesige Fakultäten nicht direkt aufgebaut werden. In C++ und Python wird \(\log_{10}(n!)\) über die Identität \(\log(n!)=\log\Gamma(n+1)\) ermittelt; die Java-Implementierung verwendet die äquivalente Summe \(\sum_{k=1}^{n}\log_{10} k\).
Nach der Berechnung von \(\log_{10}S\) schreibt die Implementierung
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
sodass
$$S=10^{\theta}\times 10^{e}.$$
Dann wird die Mantisse \(10^{\theta}\) auf genau 10 Nachkommastellen gerundet. Eine abschließende Übertragsprüfung ist nötig, weil Rundung aus einer Mantisse wie \(9.99999999996\) den Wert \(10.0000000000\) machen kann; das muss als \(1.0000000000\times 10^{e+1}\) normalisiert werden. Die C++-Implementierung prüft zusätzlich die kleinen Fälle \(S(2,2)\) und \(S(2,3)\), bevor das Ergebnis für \((5,8)\) ausgegeben wird.
Für den festen Project-Euler-Zielwert ist die Berechnung in allen drei Sprachen effektiv \(O(1)\) in Zeit und Speicher. Allgemeiner hat die mathematische Formel konstante Größe, sobald die benötigten Logarithmen der Fakultäten vorliegen. Die C++- und Python-Versionen erhalten diese Werte mit konstant vielen Bibliotheksaufrufen; die Java-Version summiert Dezimallogarithmen bis \(ab\), benötigt dabei aber ebenfalls nur \(O(1)\) zusätzlichen Speicher.
Başlangıçta birim alanlı bir dikdörtgen vardır. Toplam \(ab\) tur boyunca Alex mevcut dikdörtgeni \(a\times b\) ızgaraya böler; kesimler çakışabildiği için bazı şeritlerin genişliği veya yüksekliği \(0\) olabilir. Bianca ise daha önce kullanılmamış bir hücre etiketini seçer ve oyun seçilen hücrenin içinde devam eder. Alex son alanı olabildiğince büyük tutmak, Bianca ise olabildiğince küçültmek ister. Optimal oyundaki ortak değer \(S(a,b)\) ile gösterilir.
C++, Python ve Java uygulamaları büyük bir minimaks ağacını dolaşmaz. Bunun yerine \(S(a,b)\) için kapalı formülü kullanır ve sonra bu değeri \((a,b)=(5,8)\) için sayısal olarak hesaplar.
Kritik gözlem, geometrinin temiz biçimde yatay oyun ve dikey oyun olarak ayrılmasıdır. Bu iki tek boyutlu alt oyun çözüldüğünde tüm dikdörtgenin değeri doğrudan çıkar.
\(t\). turda sütun genişlikleri \(x_1^{(t)},\dots,x_a^{(t)}\) olsun ve
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
satır yükseklikleri de \(y_1^{(t)},\dots,y_b^{(t)}\) olsun ve
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
Bianca \(i_t\) sütunundaki ve \(j_t\) satırındaki hücreyi seçerse, o tur kalan alan
$$x_{i_t}^{(t)}y_{j_t}^{(t)}$$
katsayısı ile çarpılır. Böylece \(ab\) turun sonunda son alan
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right)$$
olur. Yani iki boyutlu oyun, yatay katkı ile dikey katkının çarpımına ayrılır.
\(ab\) hücre etiketini \((i,j)\) çiftleri olarak düşünebiliriz; burada \(1\le i\le a\) ve \(1\le j\le b\). Oyun tam \(ab\) tur sürdüğü ve Bianca bir etiketi tekrar kullanamadığı için, sonunda her çift tam bir kez kullanılmış olur.
Bundan şu toplam kullanım sayıları zorunlu olarak çıkar:
$$\text{her sütun indeksi }i\text{ tam }b\text{ kez görünür},$$
$$\text{her satır indeksi }j\text{ tam }a\text{ kez görünür}.$$
Dolayısıyla yatay parça, her biri \(b\) kez seçilmek zorunda olan \(a\) etiketli tek boyutlu bir aralık oyunudur. Dikey parça da her biri \(a\) kez seçilmek zorunda olan \(b\) etiketli aynı yapıdır.
Şimdi aşağıdaki niceliği tanımlayalım:
$$T_n(r_1,\dots,r_n)$$
ifadesi, \(i\) etiketinin daha \(r_i\) kez seçilmesi gereken aralık oyununun optimal değerini göstersin. Şunu yazalım:
$$R=r_1+\cdots+r_n.$$
Alex mevcut aralığı \(x_1,\dots,x_n\) uzunluklarına bölsün; burada \(x_i\ge 0\) ve \(\sum x_i=1\). Bianca da \(r_i>0\) olan etiketlerden birini seçsin. O zaman devam değeri
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)$$
olur. Böylece minimaks bağıntısı
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)$$
şeklindedir.
Optimal bölmede, şu anda mümkün olan her seçim aynı devam değerini vermelidir. Aksi halde Alex biraz uzunluğu daha büyük değerden alıp daha küçük değere aktararak minimumu büyütebilir. Bu yüzden her aktif \(i\) için
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
olacak tek bir sabit \(\lambda\) vardır. Buradan
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}$$
elde edilir. Aktif etiketler üzerinde toplayınca
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}$$
ve dolayısıyla
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}$$
çıkar.
Bu bağıntının çözümü
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}$$
şeklindedir. Gerçekten yerine koyarsak
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
dolayısıyla
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
ve bunun tersi tam olarak \(\frac{\prod r_i!}{R!}\) olur. Buna karşılık gelen optimal bölme de çok sadedir:
$$x_i=\frac{r_i}{R}.$$
Yani her aktif şerit, gelecekte kaç kez seçilmesi gerekiyorsa o oranda uzunluk alır; tamamen tükenmiş etiketlere ise kesimler çakışabildiği için \(0\) genişlik verilebilir.
Yatay oyunun başında \(a\) etiket vardır ve her biri \(b\) kez seçilecektir. Bu yüzden
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
Dikey oyunun başında \(b\) etiket vardır ve her biri \(a\) kez seçilecektir. Bu yüzden
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
İki bağımsız çarpanı çarptığımızda
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
sonucu elde edilir. Uygulamaların kullandığı formül tam olarak budur.
\((a,b)=(2,2)\) için tek boyutlu değer
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6}$$
olur. Bu yüzden
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
\((a,b)=(2,3)\) için iki çarpan
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90}$$
olur ve dolayısıyla
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
ki bu da bilinen kontrol değerleriyle aynıdır.
C++, Python ve Java uygulamalarının tamamı yukarıdaki kapalı formülü kullanır; tam oyun ağacını gezmezler. Hesaplanan temel ifade
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!)$$
şeklindedir. Böylece çok büyük faktöriyel değerlerini doğrudan üretmeye gerek kalmaz. C++ ve Python tarafında \(\log_{10}(n!)\), \(\log(n!)=\log\Gamma(n+1)\) özdeşliğiyle elde edilir; Java tarafında ise buna eşdeğer olan \(\sum_{k=1}^{n}\log_{10} k\) toplamı kullanılır.
\(\log_{10}S\) bulunduktan sonra uygulama
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1$$
yazar ve böylece
$$S=10^{\theta}\times 10^{e}$$
elde edilir. Ardından mantissa \(10^{\theta}\) tam 10 ondalık basamağa yuvarlanır. Yuvarlama sonucunda \(9.99999999996\) gibi bir mantissa \(10.0000000000\) değerine sıçrayabilir; bu durumda sonuç \(1.0000000000\times 10^{e+1}\) biçiminde yeniden normalize edilir. C++ uygulaması ayrıca \((2,2)\) ve \((2,3)\) küçük örneklerini de kontrol edip sonra \((5,8)\) sonucunu basar.
Sabit Project Euler girdisi için hesaplama üç dilde de pratikte \(O(1)\) zaman ve \(O(1)\) bellek kullanır. Daha genel bakışla, gerekli log-faktöriyel değerleri hazır olduğunda matematiksel formülün kendisi sabit boyutludur. C++ ve Python bu değerleri sabit sayıda kütüphane çağrısıyla elde eder; Java ise \(ab\)'ye kadar onluk log toplamı alır, ama yine yalnızca \(O(1)\) ek bellek kullanır.
Se parte de un rectángulo unidad. En cada una de las \(ab\) rondas, Alex divide el rectángulo actual en una malla \(a\times b\); los cortes pueden coincidir, así que algunas franjas pueden tener anchura o altura \(0\). Bianca elige entonces una etiqueta de celda que no haya usado antes, y el juego continúa dentro de esa celda. Alex quiere maximizar el área final, Bianca quiere minimizarla, y el valor común bajo juego óptimo se denota por \(S(a,b)\).
Las implementaciones en C++, Python y Java no recorren explícitamente un árbol minimax. En su lugar usan una fórmula cerrada para \(S(a,b)\) y luego la evalúan numéricamente para \((a,b)=(5,8)\).
La observación decisiva es que la geometría del problema se separa con limpieza en un juego horizontal y otro vertical. Una vez resueltos esos subjuegos unidimensionales, el valor del rectángulo completo sale de inmediato.
En la ronda \(t\), sean \(x_1^{(t)},\dots,x_a^{(t)}\) las anchuras de las columnas, con
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
y sean \(y_1^{(t)},\dots,y_b^{(t)}\) las alturas de las filas, con
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
Si Bianca elige la celda de la columna \(i_t\) y la fila \(j_t\), el área restante se multiplica en esa ronda por
$$x_{i_t}^{(t)}y_{j_t}^{(t)}.$$
Tras las \(ab\) rondas, el área final vale
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
Por tanto, el juego bidimensional se factoriza en una contribución horizontal por una contribución vertical.
Podemos ver las \(ab\) etiquetas de celda como los pares \((i,j)\), con \(1\le i\le a\) y \(1\le j\le b\). Como el juego dura exactamente \(ab\) rondas y Bianca no puede reutilizar una etiqueta, cada par se usa exactamente una vez al final.
Eso fija automáticamente las multiplicidades totales:
$$\text{cada índice de columna }i\text{ aparece exactamente }b\text{ veces},$$
$$\text{cada índice de fila }j\text{ aparece exactamente }a\text{ veces}.$$
Así, la parte horizontal es un juego unidimensional de intervalos con \(a\) etiquetas, cada una exigida \(b\) veces, y la parte vertical es la misma construcción con \(b\) etiquetas, cada una exigida \(a\) veces.
Sea
$$T_n(r_1,\dots,r_n)$$
el valor óptimo de la versión unidimensional cuando la etiqueta \(i\) todavía debe elegirse \(r_i\) veces más. Escribimos
$$R=r_1+\cdots+r_n.$$
Si Alex divide el intervalo actual en longitudes \(x_1,\dots,x_n\), con \(x_i\ge 0\) y \(\sum x_i=1\), Bianca elige cualquier índice con \(r_i>0\). El valor de continuación es entonces
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
Por ello, la recurrencia minimax es
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
En una partición óptima, toda elección actualmente disponible debe producir el mismo valor. Si no fuera así, Alex podría mover una pequeña parte de longitud desde una rama más grande hacia otra más pequeña y mejorar el mínimo. Por tanto, para todo \(i\) activo,
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
para una constante común \(\lambda\). De ahí
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
Sumando sobre las etiquetas activas se obtiene
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
y por tanto
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
La solución de la recurrencia es
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
En efecto, al sustituirla resulta
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
así que
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
cuyo recíproco es exactamente \(\frac{\prod r_i!}{R!}\). La partición óptima correspondiente es muy simple:
$$x_i=\frac{r_i}{R}.$$
Es decir, cada franja activa recibe una longitud proporcional al número de veces que todavía debe ser elegida; las etiquetas agotadas pueden recibir anchura \(0\) porque los cortes pueden coincidir.
Al inicio del juego horizontal hay \(a\) etiquetas y cada una debe usarse \(b\) veces, por lo que
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
Al inicio del juego vertical hay \(b\) etiquetas y cada una debe usarse \(a\) veces, por lo que
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
Multiplicando ambos factores independientes se obtiene
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
Esa es exactamente la fórmula utilizada por las implementaciones.
Para \((a,b)=(2,2)\), el valor unidimensional es
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
de modo que
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
Para \((a,b)=(2,3)\), los dos factores son
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
y entonces
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
en acuerdo con los valores de comprobación.
Las implementaciones en C++, Python y Java usan la fórmula cerrada anterior en lugar de recorrer el árbol completo del juego. Evalúan
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
Así se evita construir factoriales enormes de forma directa. En C++ y Python, \(\log_{10}(n!)\) se obtiene mediante la identidad \(\log(n!)=\log\Gamma(n+1)\); la implementación en Java usa la suma equivalente \(\sum_{k=1}^{n}\log_{10} k\).
Después de calcular \(\log_{10}S\), la implementación escribe
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
de modo que
$$S=10^{\theta}\times 10^{e}.$$
La mantisa \(10^{\theta}\) se redondea entonces a exactamente 10 cifras decimales. Hace falta una comprobación final de acarreo, porque un valor como \(9.99999999996\) puede redondearse a \(10.0000000000\); en ese caso debe renormalizarse como \(1.0000000000\times 10^{e+1}\). La implementación en C++ además verifica los casos pequeños \(S(2,2)\) y \(S(2,3)\) antes de imprimir el resultado de \((5,8)\).
Para la entrada fija de Project Euler, el cálculo es efectivamente \(O(1)\) en tiempo y \(O(1)\) en memoria en los tres lenguajes. Más en general, la propia fórmula matemática tiene tamaño constante una vez disponibles los tres log-factoriales necesarios. Las versiones en C++ y Python los obtienen con un número constante de llamadas de biblioteca; la versión en Java los calcula sumando logaritmos decimales hasta \(ab\), y aun así utiliza solo \(O(1)\) memoria extra.
起点是一个单位矩形。在总共 \(ab\) 轮操作中，Alex 每一轮都把当前矩形切成一个 \(a\times b\) 的网格；题目允许切线重合，因此某些条带的宽度或高度可以是 \(0\)。随后 Bianca 选择一个此前从未用过的格子标签，游戏就在那一个格子内部继续进行。Alex 想让最后剩下的面积尽可能大，Bianca 想让它尽可能小，双方最优对抗下的共同值记为 \(S(a,b)\)。
C++、Python 和 Java 实现都没有去展开庞大的 minimax 博弈树，而是先用一个闭式公式刻画 \(S(a,b)\)，再把 \((a,b)=(5,8)\) 代入并以科学计数法输出。
真正关键的地方在于：这个二维切割博弈可以严格拆成一个水平方向的一维博弈和一个竖直方向的一维博弈。只要把一维版本求出来，二维结论就会直接落下。
设第 \(t\) 轮时，列宽分别为 \(x_1^{(t)},\dots,x_a^{(t)}\)，满足
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
行高分别为 \(y_1^{(t)},\dots,y_b^{(t)}\)，满足
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
如果 Bianca 在这一轮选中第 \(i_t\) 列、第 \(j_t\) 行对应的那个格子，那么当前剩余面积会乘上
$$x_{i_t}^{(t)}y_{j_t}^{(t)}.$$
于是经过全部 \(ab\) 轮之后，最终面积就是
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
这说明二维问题天然分解成“所有被选列宽的乘积”和“所有被选行高的乘积”的乘法结构。
把 \(ab\) 个格子标签看成所有可能的有序对 \((i,j)\)，其中 \(1\le i\le a\)、\(1\le j\le b\)。由于游戏一共进行 \(ab\) 轮，而且 Bianca 不能重复使用标签，所以到游戏结束时，每一个 \((i,j)\) 都恰好被用过一次。
于是总出现次数立刻固定下来：
$$\text{每个列索引 }i\text{ 恰好出现 }b\text{ 次},$$
$$\text{每个行索引 }j\text{ 恰好出现 }a\text{ 次}.$$
因此，水平方向可以单独看成一个一维区间博弈：一共有 \(a\) 个标签，每个标签必须被选中 \(b\) 次。竖直方向完全类似，只是变成 \(b\) 个标签，每个标签必须被选中 \(a\) 次。
记
$$T_n(r_1,\dots,r_n)$$
为这样一个一维问题的最优值：当前有 \(n\) 个标签，而第 \(i\) 个标签未来还必须再被选中 \(r_i\) 次。再记
$$R=r_1+\cdots+r_n.$$
如果 Alex 这一轮把当前区间切成长度 \(x_1,\dots,x_n\) 的 \(n\) 段，其中 \(x_i\ge 0\) 且 \(\sum x_i=1\)，那么 Bianca 会从所有 \(r_i>0\) 的标签里挑一个。若她选的是第 \(i\) 个标签，剩余长度因子就变成
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
所以一维 minimax 递推是
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
这一步把原题的“切矩形”问题精确地降成了一个只关心区间长度分配的一维博弈。
在最优切分下，所有当前仍可被选择的标签都必须给出同样的后续值。原因很直接：如果某个分支明显更大、另一个分支明显更小，那么 Alex 就可以把一点点长度从较大分支移到较小分支，从而抬高最小值。于是对每个活跃的 \(i\) 都有
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
这里 \(\lambda\) 是同一个常数。因此
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
把所有活跃标签的长度加总为 \(1\)，得到
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
于是
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
也就是说，一维值满足一个非常整齐的“倒数求和再取倒数”的关系。
上面的递推恰好由下面这个表达式解决：
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
验证并不复杂。把候选式代回去：
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i.$$
于是
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
其倒数正好就是 \(\frac{\prod r_i!}{R!}\)。因此闭式成立。更进一步，最优切分比例也随之直接读出：
$$x_i=\frac{r_i}{R}.$$
也就是说，某个标签未来还要出现多少次，就应该给它分配相应比例的长度。那些已经不再需要的标签可以拿到宽度 \(0\)，这与题目允许切线重合完全一致。
在水平方向，一开始有 \(a\) 个标签，而且每个标签最终都必须出现 \(b\) 次，所以
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
在竖直方向，一开始有 \(b\) 个标签，而且每个标签最终都必须出现 \(a\) 次，所以
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
二维矩形的最终面积值就是这两个独立因子的乘积：
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
这正是实现所使用的核心公式。
当 \((a,b)=(2,2)\) 时，一维值为
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
因此
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
当 \((a,b)=(2,3)\) 时，水平方向与竖直方向分别是
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
所以
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
和已知校验值完全一致。
C++、Python 和 Java 实现都直接使用上面的闭式公式，而不是去枚举整棵博弈树。它们计算的核心量是
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
这样做可以避免直接构造巨大阶乘。C++ 和 Python 通过恒等式 \(\log(n!)=\log\Gamma(n+1)\) 来得到 \(\log_{10}(n!)\)；Java 则使用与之等价的求和形式 \(\sum_{k=1}^{n}\log_{10} k\)。
得到 \(\log_{10}S\) 之后，程序把它写成
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
于是
$$S=10^{\theta}\times 10^{e}.$$
接下来把尾数 \(10^{\theta}\) 四舍五入到恰好 10 位小数，并单独处理一次进位边界。因为像 \(9.99999999996\) 这样的值在四舍五入后会变成 \(10.0000000000\)，这时必须重新规范化成 \(1.0000000000\times 10^{e+1}\)。另外，C++ 实现还会先验证两个小样例 \(S(2,2)\) 和 \(S(2,3)\)，然后才输出 \((5,8)\) 的结果。
对于题目固定的目标输入，三种实现都可以视为 \(O(1)\) 时间、\(O(1)\) 额外空间。更一般地说，一旦所需的几个对数阶乘已经得到，数学公式本身就是常数规模。C++ 与 Python 通过常数次库调用获得这些值；Java 版本通过累加到 \(ab\) 的十进制对数来得到它们，但额外空间仍然是 \(O(1)\)。
Игра начинается с единичного прямоугольника. В каждом из \(ab\) раундов Алекс разбивает текущий прямоугольник на сетку \(a\times b\); разрезы могут совпадать, поэтому некоторые полосы могут иметь нулевую ширину или высоту. Затем Бианка выбирает метку клетки, которая еще не использовалась, и игра продолжается внутри выбранной клетки. Алекс стремится максимизировать конечную площадь, Бианка стремится минимизировать ее, а общий оптимальный результат обозначается \(S(a,b)\).
Реализации на C++, Python и Java не перебирают весь minimax-дерево. Вместо этого они используют замкнутую формулу для \(S(a,b)\), а затем вычисляют ее численно для \((a,b)=(5,8)\).
Ключевое наблюдение состоит в том, что геометрия задачи естественно раскладывается на горизонтальную и вертикальную одномерные игры. После решения этих подзадач формула для исходного прямоугольника получается сразу.
Пусть в раунде \(t\) ширины столбцов равны \(x_1^{(t)},\dots,x_a^{(t)}\), где
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
а высоты строк равны \(y_1^{(t)},\dots,y_b^{(t)}\), где
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
Если Бианка выбирает клетку в столбце \(i_t\) и строке \(j_t\), то в этом раунде оставшаяся площадь умножается на
$$x_{i_t}^{(t)}y_{j_t}^{(t)}.$$
После всех \(ab\) раундов конечная площадь равна
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
Итак, двумерная игра раскладывается в произведение горизонтального и вертикального вкладов.
Удобно считать, что \(ab\) меток клеток соответствуют парам \((i,j)\), где \(1\le i\le a\) и \(1\le j\le b\). Поскольку игра длится ровно \(ab\) ходов, а повторно выбирать метку нельзя, в конце каждая пара используется ровно один раз.
Отсюда автоматически следуют суммарные кратности:
$$\text{каждый индекс столбца }i\text{ встречается ровно }b\text{ раз},$$
$$\text{каждый индекс строки }j\text{ встречается ровно }a\text{ раз}.$$
Следовательно, горизонтальная часть есть одномерная интервальная игра с \(a\) метками, каждая из которых должна быть выбрана \(b\) раз, а вертикальная часть устроена аналогично для \(b\) меток, каждая из которых нужна \(a\) раз.
Обозначим через
$$T_n(r_1,\dots,r_n)$$
оптимальное значение одномерной версии, если метка \(i\) должна быть выбрана еще \(r_i\) раз. Также введем
$$R=r_1+\cdots+r_n.$$
Если Алекс делит текущий отрезок на части длины \(x_1,\dots,x_n\), где \(x_i\ge 0\) и \(\sum x_i=1\), то Бианка выбирает любой индекс с \(r_i>0\). Тогда значение продолжения равно
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
Поэтому minimax-рекурсия имеет вид
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
В оптимальном разбиении все доступные в данный момент варианты должны давать одно и то же значение. Иначе Алекс смог бы перенести немного длины от более сильной ветви к более слабой и увеличить минимум. Значит, для каждого активного \(i\)
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
с одной и той же константой \(\lambda\). Отсюда
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
Суммируя по всем активным меткам, получаем
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
а значит
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
Эта рекурсия решается выражением
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
Действительно, подстановка дает
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
поэтому
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
а его обратное значение равно ровно \(\frac{\prod r_i!}{R!}\). Соответствующее оптимальное разбиение тоже получается очень простым:
$$x_i=\frac{r_i}{R}.$$
То есть каждой активной полосе выделяется длина, пропорциональная числу будущих обязательных выборов; исчерпанные метки могут получить нулевую ширину, потому что совпадающие разрезы разрешены.
В начале горизонтальной игры есть \(a\) меток, каждая из которых должна встретиться \(b\) раз, следовательно
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
В начале вертикальной игры есть \(b\) меток, каждая из которых должна встретиться \(a\) раз, следовательно
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
Перемножая два независимых множителя, получаем
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
Именно эту формулу используют реализации.
Для \((a,b)=(2,2)\) одномерное значение равно
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
поэтому
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
Для \((a,b)=(2,3)\) горизонтальный и вертикальный множители равны
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
следовательно
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
что совпадает с контрольными значениями.
Реализации на C++, Python и Java используют приведенную выше замкнутую формулу вместо обхода полной игровой дерева. Они вычисляют
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
Это позволяет не строить огромные факториалы напрямую. В C++ и Python значение \(\log_{10}(n!)\) берется из тождества \(\log(n!)=\log\Gamma(n+1)\); в Java используется эквивалентная сумма \(\sum_{k=1}^{n}\log_{10} k\).
После нахождения \(\log_{10}S\) программа записывает
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
так что
$$S=10^{\theta}\times 10^{e}.$$
Затем мантисса \(10^{\theta}\) округляется ровно до 10 знаков после запятой. Нужна дополнительная проверка переноса, потому что значение вроде \(9.99999999996\) после округления превращается в \(10.0000000000\), и его следует перенормировать как \(1.0000000000\times 10^{e+1}\). Реализация на C++ также отдельно проверяет случаи \(S(2,2)\) и \(S(2,3)\), прежде чем печатать результат для \((5,8)\).
Для фиксированного целевого входа Project Euler вычисление фактически занимает \(O(1)\) времени и \(O(1)\) памяти во всех трех языках. В более общем виде сама формула имеет постоянный размер, как только доступны нужные логарифмы факториалов. В версиях C++ и Python они получаются за константное число библиотечных вызовов; версия Java вычисляет их суммированием десятичных логарифмов до \(ab\), но тоже использует лишь \(O(1)\) дополнительной памяти.
نبدأ بمستطيل وحدي. في كل واحدة من الجولات \(ab\)، يقسم أليكس المستطيل الحالي إلى شبكة \(a\times b\). وبما أن مواضع القطع قد تتطابق، فمن المسموح أن تكون بعض الشرائط ذات عرض أو ارتفاع يساوي \(0\). بعد ذلك تختار بيانكا وسم خلية لم يُستخدم من قبل، ثم يستمر اللعب داخل تلك الخلية المختارة. أليكس يريد أن يجعل المساحة النهائية أكبر ما يمكن، وبيانكا تريد أن تجعلها أصغر ما يمكن، والقيمة المشتركة تحت اللعب الأمثل نرمز لها بـ \(S(a,b)\).
تنفيذات C++ وPython وJava لا تستعرض شجرة minimax كاملة. بدلاً من ذلك تعتمد على صيغة مغلقة لقيمة \(S(a,b)\)، ثم تحسبها عددياً للحالة \((a,b)=(5,8)\).
الفكرة الحاسمة هي أن البنية الهندسية للمسألة تنفصل بوضوح إلى لعبة أفقية ولعبة رأسية من بعد واحد. وما إن نحل هاتين اللعبتين الجزئيتين، تصبح قيمة المسألة الأصلية نتيجة مباشرة.
في الجولة \(t\)، لتكن عروض الأعمدة هي \(x_1^{(t)},\dots,x_a^{(t)}\) بحيث
$$x_1^{(t)}+\cdots+x_a^{(t)}=1,$$
ولتكن ارتفاعات الصفوف هي \(y_1^{(t)},\dots,y_b^{(t)}\) بحيث
$$y_1^{(t)}+\cdots+y_b^{(t)}=1.$$
إذا اختارت بيانكا الخلية الواقعة في العمود \(i_t\) والصف \(j_t\)، فإن المساحة المتبقية تُضرب في تلك الجولة بالعامل
$$x_{i_t}^{(t)}y_{j_t}^{(t)}.$$
وبعد جميع الجولات \(ab\)، تصبح المساحة النهائية
$$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$$
إذن اللعبة ثنائية الأبعاد تتحلل إلى حاصل ضرب مساهمة أفقية ومساهمة رأسية.
يمكن النظر إلى وسوم الخلايا \(ab\) على أنها الأزواج \((i,j)\) حيث \(1\le i\le a\) و\(1\le j\le b\). وبما أن اللعبة تستمر \(ab\) جولة تماماً ولا يجوز لبيانكا إعادة استخدام وسم، فإن كل زوج يُستخدم مرة واحدة بالضبط عند نهاية اللعبة.
ومن هنا تُثبت المضاعفات الكلية تلقائياً: كل فهرس عمود يظهر في المجموع \(b\) مرات، وكل فهرس صف يظهر في المجموع \(a\) مرات.
لذلك يصبح الجزء الأفقي لعبة فترات أحادية البعد فيها \(a\) وسوماً، وكل وسم يجب أن يُختار \(b\) مرات. والجزء الرأسي هو البناء نفسه لكن مع \(b\) وسوماً، وكل واحد منها يجب أن يُختار \(a\) مرات.
لنرمز بـ
$$T_n(r_1,\dots,r_n)$$
إلى القيمة المثلى للنسخة الأحادية عندما يبقى على الوسم \(i\) أن يُختار \(r_i\) مرة إضافية. ولنكتب
$$R=r_1+\cdots+r_n.$$
إذا قسّم أليكس الفترة الحالية إلى أطوال \(x_1,\dots,x_n\) مع \(x_i\ge 0\) و\(\sum x_i=1\)، فإن بيانكا تختار أي وسم له \(r_i>0\). وعندئذ تكون قيمة الاستمرار
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
وبالتالي تكون علاقة minimax هي
$$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$$
في التقسيم الأمثل، لا بد أن تعطي كل الخيارات النشطة حالياً القيمة نفسها. ولو لم يحدث ذلك، لاستطاع أليكس أن ينقل جزءاً صغيراً من الطول من فرع أقوى إلى فرع أضعف ويرفع بذلك الحد الأدنى. لذلك لكل \(i\) نشط لدينا
$$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$$
لثابت مشترك \(\lambda\). ومنه
$$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$$
وبجمع الأطوال على جميع الوسوم النشطة نحصل على
$$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$$
ومن ثم
$$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$$
الحل المغلق لهذه العلاقة هو
$$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$$
والتحقق مباشر. فبالتعويض نجد
$$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$$
وبالتالي
$$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$$
ومقلوبه يساوي بالضبط \(\frac{\prod r_i!}{R!}\). كما أن التقسيم الأمثل نفسه يصبح بسيطاً جداً:
$$x_i=\frac{r_i}{R}.$$
أي أن كل شريط نشط يأخذ طولاً متناسباً مع عدد المرات التي ما زال يجب اختياره فيها. أما الوسوم المنتهية فيمكن إعطاؤها عرضاً صفرياً لأن تطابق مواضع القطع مسموح.
في بداية اللعبة الأفقية توجد \(a\) وسوم، وكل واحد منها يجب أن يظهر \(b\) مرات، لذلك
$$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$$
وفي بداية اللعبة الرأسية توجد \(b\) وسوم، وكل واحد منها يجب أن يظهر \(a\) مرات، لذلك
$$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$$
وبضرب العاملين المستقلين نحصل على
$$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$$
وهذه هي الصيغة نفسها التي تعتمدها التنفيذات.
عندما \((a,b)=(2,2)\)، تكون القيمة الأحادية
$$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$$
ومن ثم
$$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$$
وعندما \((a,b)=(2,3)\)، يكون العاملان
$$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$$
وبالتالي
$$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$$
وهو ما يطابق قيم التحقق المعروفة.
تنفيذات C++ وPython وJava كلها تستخدم الصيغة المغلقة أعلاه بدلاً من استعراض شجرة اللعبة كاملة. والكمية الأساسية التي تُحسب هي
$$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$$
وهذا يمنع التعامل المباشر مع قيم عامليات ضخمة جداً. في C++ وPython يُستخرج \(\log_{10}(n!)\) من الهوية \(\log(n!)=\log\Gamma(n+1)\)، بينما يستخدم تنفيذ Java المجموع المكافئ \(\sum_{k=1}^{n}\log_{10} k\).
بعد حساب \(\log_{10}S\)، تكتب الشيفرة
$$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$$
بحيث
$$S=10^{\theta}\times 10^{e}.$$
ثم تُقرَّب المانتيسا \(10^{\theta}\) إلى 10 منازل عشرية بالضبط، مع فحص أخير لحالة الحمل. فالقيمة \(9.99999999996\) مثلاً قد تُقرَّب إلى \(10.0000000000\)، وعندها يجب إعادة التطبيع إلى \(1.0000000000\times 10^{e+1}\). كما أن تنفيذ C++ يتحقق أيضاً من الحالتين الصغيرتين \(S(2,2)\) و\(S(2,3)\) قبل طباعة ناتج \((5,8)\).
بالنسبة إلى إدخال Project Euler الثابت، يكون الحساب فعلياً \(O(1)\) زمنياً و\(O(1)\) من حيث الذاكرة في اللغات الثلاث كلها. وبصورة أعم، فإن الصيغة الرياضية نفسها ذات حجم ثابت ما دامت القيم اللوغاريتمية للعوامليات المطلوبة متاحة. نسختا C++ وPython تحصلان على هذه القيم بعدد ثابت من نداءات المكتبة، أما نسخة Java فتحسبها بجمع لوغاريتمات عشرية حتى \(ab\)، لكنها لا تزال تستخدم \(O(1)\) مساحة إضافية فقط.