For an \(m \times n\) grid, we count every axis-aligned sub-rectangle. The target is \(2{,}000{,}000\) rectangles, but the problem asks for the grid whose count is closest to that value, not necessarily equal to it. The closest grid is \(36 \times 77\) (or \(77 \times 36\)), which contains \(1{,}999{,}998\) rectangles and therefore has area \(2772\).
The key observation is that a sub-rectangle is determined entirely by its boundary lines. Once that is written down, the geometry collapses to a product of two triangular numbers, and the remaining task is a very small monotone search.
An \(m \times n\) grid has \(m+1\) horizontal grid lines and \(n+1\) vertical grid lines. To form a sub-rectangle, choose two distinct horizontal lines and two distinct vertical lines. Therefore
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
If we denote the \(k\)-th triangular number by \(T_k=k(k+1)/2\), then the count becomes
$$R(m,n)=T_mT_n.$$
This is the central mathematical object of the problem: every candidate grid corresponds to a product of two triangular numbers.
The closed form also appears if we count by size. A rectangle of height \(h\) and width \(w\) can start in \(m-h+1\) vertical positions and \(n-w+1\) horizontal positions, so
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
Because the horizontal and vertical choices are independent, the double sum factors as
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
The implementations use this factorized form directly, so each candidate can be evaluated with constant-time arithmetic.
For \(m=3\) and \(n=2\), we get
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
So a \(3 \times 2\) grid contains exactly 18 sub-rectangles and has area \(6\). This is a useful check because it can be verified by hand and matches the sample behavior built into the solutions.
The count is symmetric:
$$R(m,n)=R(n,m).$$
That means we only need to examine pairs with \(m \le n\). For fixed \(m\), the count grows strictly with \(n\):
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
Once a fixed row of candidates has crossed the target, larger values of \(n\) only move farther away, so the inner search can stop early. The implementations also use a generous hard cap of \(2000\); this is already beyond the scale where even a \(1 \times 2000\) strip has
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
rectangles, so the optimum is safely contained inside that window.
After the problem has been reduced to minimizing
$$\left|T_mT_n-2{,}000{,}000\right|,$$
the best pair found by the implementations is
$$m=36,\qquad n=77.$$
Indeed,
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
so the target is missed by only \(2\). The reported area is therefore
$$36 \cdot 77=2772.$$
The C++, Python, and Java implementations all perform the same search. They iterate over the smaller side first and then iterate over the larger side starting from that value, which avoids visiting both \((m,n)\) and \((n,m)\). For each pair, they compute \(R(m,n)=m(m+1)n(n+1)/4\) and compare its absolute distance from the target with the current best distance.
Whenever a closer grid is found, the stored best area is updated. Because the rectangle count is monotone in the second dimension, the inner loop stops after the overshoot point instead of scanning the rest of the row. One implementation writes that stopping condition a little more conservatively and also includes a small sample checkpoint plus an optional target override, but the mathematical core is identical in all three languages.
If the outer cap is \(B\), then symmetry reduces the worst-case search to the pairs \(1 \le m \le n \le B\), which is at most
$$\frac{B(B+1)}{2}$$
candidate grids. With the literal bound \(B=2000\), that is \(2{,}001{,}000\) evaluations before early termination is even taken into account.
Each evaluation uses only constant-time integer arithmetic, so the worst-case running time is \(O(B^2)\) and the memory usage is \(O(1)\). In practice the code is faster than the raw bound suggests because the monotone inner loop usually breaks well before reaching the cap.
Für ein \(m \times n\)-Gitter sollen alle achsenparallelen Teilrechtecke gezählt werden. Das Ziel ist \(2{,}000{,}000\) Rechtecke, aber gesucht ist nicht unbedingt ein exakter Treffer, sondern das Gitter mit der kleinsten Abweichung. Das beste Gitter ist \(36 \times 77\) (oder \(77 \times 36\)); es enthält \(1{,}999{,}998\) Teilrechtecke und hat daher die Fläche \(2772\).
Der entscheidende Gedanke ist, dass ein Teilrechteck vollständig durch seine Randlinien festgelegt wird. Dadurch wird das geometrische Problem zu einem Produkt zweier Dreieckszahlen, und danach bleibt nur noch eine kleine monotone Suche.
Ein \(m \times n\)-Gitter besitzt \(m+1\) horizontale und \(n+1\) vertikale Gitterlinien. Ein Teilrechteck entsteht, wenn man zwei verschiedene horizontale und zwei verschiedene vertikale Linien auswählt. Also gilt
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
Bezeichnet man die \(k\)-te Dreieckszahl mit \(T_k=k(k+1)/2\), dann wird daraus
$$R(m,n)=T_mT_n.$$
Genau dieses Produkt aus zwei Dreieckszahlen ist das zentrale mathematische Objekt des Problems.
Man kann dieselbe geschlossene Form auch über Höhe und Breite herleiten. Ein Rechteck der Höhe \(h\) und Breite \(w\) kann in \(m-h+1\) vertikalen und \(n-w+1\) horizontalen Positionen liegen, also
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
Da horizontale und vertikale Wahl unabhängig sind, faktorisiert die Doppelsumme zu
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
Die Implementierungen verwenden genau diese faktorierte Form, sodass jeder Kandidat in konstanter Zeit ausgewertet werden kann.
Für \(m=3\) und \(n=2\) erhält man
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
Ein \(3 \times 2\)-Gitter besitzt also genau 18 Teilrechtecke und die Fläche \(6\). Dieses Beispiel eignet sich gut als Kontrollrechnung, weil man es von Hand nachprüfen kann und weil es der kleinen Testprüfung in den Lösungen entspricht.
Die Zählfunktion ist symmetrisch:
$$R(m,n)=R(n,m).$$
Deshalb reicht es, nur Paare mit \(m \le n\) zu betrachten. Für festes \(m\) wächst die Anzahl streng mit \(n\):
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
Sobald in einer festen Zeile der Suche das Ziel überschritten wurde, entfernen sich größere \(n\)-Werte nur weiter vom Ziel, also kann die innere Schleife früh abbrechen. Die Implementierungen setzen außerdem eine großzügige Obergrenze von \(2000\); bereits ein \(1 \times 2000\)-Streifen hat
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
Rechtecke, daher liegt das Optimum sicher innerhalb dieses Fensters.
Nach der Reduktion auf das Minimieren von
$$\left|T_mT_n-2{,}000{,}000\right|$$
finden die Implementierungen das Paar
$$m=36,\qquad n=77.$$
Denn es gilt
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
also beträgt die Abweichung nur \(2\). Damit ist die gesuchte Fläche
$$36 \cdot 77=2772.$$
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Suche. Zuerst wird über die kleinere Seite iteriert, dann über die größere Seite beginnend bei diesem Wert, sodass \((m,n)\) und \((n,m)\) nicht doppelt geprüft werden. Für jedes Paar wird \(R(m,n)=m(m+1)n(n+1)/4\) berechnet und mit der bisher besten Abweichung verglichen.
Sobald ein näherer Kandidat gefunden wird, wird die gespeicherte beste Fläche aktualisiert. Weil die Rechteckanzahl für festes \(m\) monoton in \(n\) wächst, endet die innere Schleife nach dem Überschreiten des Ziels statt die restliche Zeile unnötig weiter zu prüfen. Eine Implementierung formuliert diese Abbruchbedingung etwas vorsichtiger und bietet zusätzlich einen kleinen Beispieltest sowie ein veränderbares Ziel an, aber der mathematische Kern ist in allen drei Sprachen identisch.
Sei \(B\) die äußere Obergrenze. Durch die Symmetrie reduziert sich die schlimmste Fallzahl der geprüften Paare auf \(1 \le m \le n \le B\), also höchstens
$$\frac{B(B+1)}{2}$$
Kandidaten. Für die konkrete Grenze \(B=2000\) sind das \(2{,}001{,}000\) Auswertungen, noch bevor die frühen Abbrüche berücksichtigt werden.
Jede Auswertung benötigt nur konstante viele ganzzahlige Operationen, daher ist die Worst-Case-Laufzeit \(O(B^2)\) und der Speicherverbrauch \(O(1)\). Praktisch ist das Verfahren schneller, weil die monotone innere Schleife meist deutlich vor der Obergrenze endet.
\(m \times n\) boyutlu bir ızgaradaki tüm eksenlere paralel alt dikdörtgenleri sayıyoruz. Hedef \(2{,}000{,}000\) dikdörtgendir; fakat istenen şey bu sayıyı tam yakalamak değil, ona en yakın ızgarayı bulup alanını vermektir. En iyi ızgara \(36 \times 77\) boyutundadır (veya simetrik olarak \(77 \times 36\)); bu ızgarada \(1{,}999{,}998\) alt dikdörtgen vardır ve alan \(2772\) olur.
Temel fikir şudur: bir alt dikdörtgen, aslında yalnızca sınır çizgileri seçilerek belirlenir. Bu gözlem geometriyi iki üçgensel sayının çarpımına indirger; geriye de küçük ve tek yönlü bir arama kalır.
\(m \times n\) ızgarasında \(m+1\) yatay ve \(n+1\) dikey çizgi vardır. Bir alt dikdörtgen oluşturmak için iki farklı yatay çizgi ve iki farklı dikey çizgi seçmek yeterlidir. Dolayısıyla
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
\(k\). üçgensel sayıyı \(T_k=k(k+1)/2\) ile gösterirsek bu ifade
$$R(m,n)=T_mT_n$$
şekline gelir. Sorunun asıl nesnesi budur: her aday ızgara iki üçgensel sayının çarpımıyla temsil edilir.
Aynı kapalı form, dikdörtgenleri yükseklik ve genişliğe göre sayarak da çıkar. Yüksekliği \(h\), genişliği \(w\) olan bir alt dikdörtgen \(m-h+1\) düşey ve \(n-w+1\) yatay konuma yerleşebilir. Bu yüzden
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
Yatay ve dikey seçimler bağımsız olduğu için çift toplam çarpana ayrılır:
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
Uygulamalar da doğrudan bu çarpanlı biçimi kullanır; böylece her aday sabit zamanda hesaplanır.
\(m=3\) ve \(n=2\) için
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18$$
olur. Yani \(3 \times 2\) bir ızgarada tam 18 alt dikdörtgen vardır ve alan \(6\) eder. Bu örnek önemlidir; çünkü hem elle doğrulanabilir hem de çözümlerde kullanılan küçük kontrol vakasıyla birebir örtüşür.
Sayım fonksiyonu simetriktir:
$$R(m,n)=R(n,m).$$
Bu nedenle yalnızca \(m \le n\) olan çiftleri incelemek yeterlidir. Sabit \(m\) için sayı \(n\) arttıkça kesin olarak büyür:
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
Demek ki sabit bir \(m\) satırında hedef aşıldıktan sonra daha büyük \(n\) değerleri yalnızca daha kötüleşir; iç döngü erken kırılabilir. Çözümler ayrıca \(2000\) gibi rahat bir üst sınır kullanır. Zaten \(1 \times 2000\) şeridi için bile
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
olduğundan optimum bu pencerenin güvenli biçimde içindedir.
Problem artık
$$\left|T_mT_n-2{,}000{,}000\right|$$
ifadesini küçültmeye indirgenmiştir. Uygulamaların bulduğu en iyi çift
$$m=36,\qquad n=77$$
olur. Çünkü
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
yani hedefe uzaklık yalnızca \(2\)'dir. Dolayısıyla istenen alan
$$36 \cdot 77=2772$$
olarak raporlanır.
C++, Python ve Java uygulamaları aynı aramayı yapar. Önce küçük kenar üzerinden ilerlenir, sonra büyük kenar o değerden başlatılır; böylece \((m,n)\) ve \((n,m)\) iki kez denenmez. Her aday için \(R(m,n)=m(m+1)n(n+1)/4\) sabit zamanda hesaplanır ve hedefe olan mutlak fark mevcut en iyi farkla karşılaştırılır.
Daha yakın bir aday bulunduğunda saklanan en iyi alan güncellenir. Dikdörtgen sayısı sabit \(m\) için \(n\) ile monoton arttığından, hedef aşıldıktan sonra satırın geri kalanı taranmaz. Bir uygulama bu durdurma koşulunu biraz daha temkinli yazar ve küçük örnek için ek bir kontrol ile değiştirilebilir hedef sunar; fakat üç dilde de matematiksel çekirdek aynıdır.
Dış sınır \(B\) olsun. Simetri sayesinde en kötü durumda yalnızca \(1 \le m \le n \le B\) çiftleri incelenir; bu da en fazla
$$\frac{B(B+1)}{2}$$
aday demektir. Somut olarak \(B=2000\) seçildiğinde erken kırılmalar hesaba katılmadan bile en fazla \(2{,}001{,}000\) değerlendirme vardır.
Her değerlendirme sabit sayıda tamsayı çarpımı ve karşılaştırma içerdiği için en kötü durum zaman maliyeti \(O(B^2)\), bellek maliyeti ise \(O(1)\)'dir. Pratikte çalışma süresi bundan daha iyidir; çünkü monoton iç döngü çoğu kez üst sınıra gelmeden biter.
En una cuadrícula \(m \times n\) hay que contar todos los subrectángulos alineados con los ejes. El objetivo es acercarse lo más posible a \(2{,}000{,}000\) rectángulos; no hace falta alcanzar ese número exactamente. La mejor cuadrícula es \(36 \times 77\) (o \(77 \times 36\)), con \(1{,}999{,}998\) subrectángulos y, por tanto, área \(2772\).
La observación clave es que un subrectángulo queda determinado por sus líneas de borde. Una vez escrita esa idea, el problema geométrico se reduce al producto de dos números triangulares, y luego solo queda una búsqueda pequeña con crecimiento monótono.
Una cuadrícula \(m \times n\) tiene \(m+1\) líneas horizontales y \(n+1\) líneas verticales. Para construir un subrectángulo basta elegir dos líneas horizontales distintas y dos líneas verticales distintas. Por eso
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
Si llamamos \(T_k=k(k+1)/2\) al \(k\)-ésimo número triangular, entonces
$$R(m,n)=T_mT_n.$$
Ese producto de dos números triangulares es el verdadero objeto matemático del problema.
La forma cerrada también aparece si se cuenta por altura y anchura. Un rectángulo de altura \(h\) y anchura \(w\) puede colocarse en \(m-h+1\) posiciones verticales y \(n-w+1\) posiciones horizontales, de modo que
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
Como las elecciones horizontal y vertical son independientes, la suma doble se separa:
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
Las implementaciones usan directamente esta forma factorizada, por lo que cada candidato se evalúa con aritmética de tiempo constante.
Si \(m=3\) y \(n=2\), entonces
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
Así, una cuadrícula \(3 \times 2\) contiene exactamente 18 subrectángulos y tiene área \(6\). Es un buen ejemplo concreto porque puede comprobarse a mano y coincide con la pequeña verificación usada por las soluciones.
La función es simétrica:
$$R(m,n)=R(n,m).$$
Por tanto solo hace falta considerar pares con \(m \le n\). Si \(m\) es fijo, el recuento crece estrictamente con \(n\):
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
En consecuencia, una vez que una fila de la búsqueda supera el objetivo, valores mayores de \(n\) solo empeoran la diferencia, y el bucle interior puede detenerse. Además, las implementaciones usan una cota superior generosa de \(2000\); incluso una franja \(1 \times 2000\) ya tiene
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
rectángulos, así que el óptimo queda con margen dentro de esa ventana.
Una vez reducido el problema a minimizar
$$\left|T_mT_n-2{,}000{,}000\right|,$$
el mejor par encontrado por las implementaciones es
$$m=36,\qquad n=77.$$
En efecto,
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
de modo que la diferencia con el objetivo es solo \(2\). El área pedida es entonces
$$36 \cdot 77=2772.$$
Las implementaciones en C++, Python y Java realizan la misma búsqueda directa. Iteran primero sobre el lado menor y luego sobre el lado mayor a partir de ese valor, lo que evita revisar dos veces tanto \((m,n)\) como \((n,m)\). Para cada pareja calculan \(R(m,n)=m(m+1)n(n+1)/4\) y comparan su distancia absoluta al objetivo con la mejor distancia observada hasta ese momento.
Cuando aparece una cuadrícula más cercana, se actualiza el área almacenada. Como el número de rectángulos es monótono en la segunda dimensión, el bucle interior se corta después del punto de sobrepaso en lugar de recorrer el resto de la fila. Una implementación escribe esa condición de parada de forma un poco más conservadora y también incorpora una pequeña comprobación de ejemplo junto con la opción de cambiar el objetivo, pero el núcleo matemático es el mismo en los tres lenguajes.
Si \(B\) es la cota exterior, la simetría reduce el peor caso a los pares \(1 \le m \le n \le B\), es decir, como máximo
$$\frac{B(B+1)}{2}$$
cuadrículas candidatas. Con la cota literal \(B=2000\), eso significa \(2{,}001{,}000\) evaluaciones antes incluso de aprovechar los cortes tempranos.
Cada evaluación usa solo unas pocas multiplicaciones y comparaciones enteras, así que el tiempo en el peor caso es \(O(B^2)\) y el espacio es \(O(1)\). En la práctica el programa es más rápido porque el bucle interior monótono suele terminar bastante antes del límite.
对于一个 \(m \times n\) 的网格，我们要统计其中所有与坐标轴平行的子矩形。目标值是 \(2{,}000{,}000\)，但题目并不要求刚好等于这个数，而是要求找到子矩形总数最接近它的网格，并输出该网格的面积。最优网格是 \(36 \times 77\)（或对称的 \(77 \times 36\)），它一共包含 \(1{,}999{,}998\) 个子矩形，因此面积为 \(2772\)。
整道题的核心在于：一个子矩形完全由它的上下边界线和左右边界线决定。把这个事实写成组合计数之后，几何问题就会化成两个三角数的乘积，剩下的只是一个很小而且单调的搜索过程。
一个 \(m \times n\) 网格有 \(m+1\) 条水平网格线和 \(n+1\) 条竖直网格线。要确定一个子矩形，只需选择两条不同的水平线，再选择两条不同的竖直线。因此有
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
如果记第 \(k\) 个三角数为 \(T_k=k(k+1)/2\)，那么公式就可以写成
$$R(m,n)=T_mT_n.$$
这就是本题真正的数学对象：每一个候选网格都对应于两个三角数的乘积。
同一个闭式公式也可以从另一种角度得到。若子矩形的高度为 \(h\)、宽度为 \(w\)，那么它可以放在 \(m-h+1\) 个竖直位置和 \(n-w+1\) 个水平位置上，于是
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
由于横向选择与纵向选择彼此独立，这个二重求和会自然分离：
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
三种实现都直接使用这个分离后的公式，因此每个候选网格只需要常数时间就能完成计算。
当 \(m=3\)、\(n=2\) 时，公式给出
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
也就是说，一个 \(3 \times 2\) 网格恰好有 18 个子矩形，面积是 \(6\)。这个例子很有价值，因为它既容易手算验证，也正好对应实现中使用的小型正确性检查。
计数函数满足对称性：
$$R(m,n)=R(n,m).$$
因此只需要考虑 \(m \le n\) 的情况。对固定的 \(m\) 来说，\(R(m,n)\) 会随着 \(n\) 严格增加：
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
这意味着，在固定 \(m\) 的一行候选值中，一旦总数超过目标，更大的 \(n\) 只会离目标更远，所以内层循环可以提前停止。实现还使用了 \(2000\) 这个宽松上界；实际上连一个 \(1 \times 2000\) 的细长网格都有
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
个子矩形，因此最优解显然已经落在这个搜索窗口之内。
把问题化为最小化
$$\left|T_mT_n-2{,}000{,}000\right|$$
之后，三种实现都找到同一个最优组合：
$$m=36,\qquad n=77.$$
因为
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
所以它与目标只差 \(2\)。题目要求输出面积，于是答案就是
$$36 \cdot 77=2772.$$
C++、Python 和 Java 的实现都采用同一套直接搜索。它们先枚举较短的一边，再从该值开始枚举较长的一边，这样就不会把 \((m,n)\) 和 \((n,m)\) 重复计算两次。对每一组边长，程序都用 \(R(m,n)=m(m+1)n(n+1)/4\) 常数时间求出子矩形总数，再与当前最优差值比较。
只要发现更接近目标的网格，程序就更新记录下来的最优面积。由于在固定 \(m\) 时计数关于 \(n\) 单调增加，内层循环在越过目标后就可以停止，而不必扫描这一整行后续的候选值。其中一个实现把停止条件写得稍微保守一些，并附带了一个小样例检查和可修改目标值的入口，但三种语言的数学核心完全一致。
设外层上界为 \(B\)。利用对称性后，最坏情况下只需要检查 \(1 \le m \le n \le B\) 的候选对，总数最多为
$$\frac{B(B+1)}{2}.$$
当 \(B=2000\) 时，即使还没有利用提前终止，候选网格数量也不过 \(2{,}001{,}000\) 个。
每次评估只包含常数次数的整数乘法与比较，所以最坏时间复杂度是 \(O(B^2)\)，空间复杂度是 \(O(1)\)。在实际运行中，由于内层循环通常会提前停止，速度还会比这个上界更快。
Для сетки размера \(m \times n\) нужно посчитать все подпрямоугольники, стороны которых параллельны осям. Цель равна \(2{,}000{,}000\), но требуется не обязательно точное совпадение, а сетка, чьё количество подпрямоугольников максимально близко к этой величине. Лучший вариант имеет размеры \(36 \times 77\) (или \(77 \times 36\)); он содержит \(1{,}999{,}998\) подпрямоугольников, а его площадь равна \(2772\).
Ключевое наблюдение состоит в том, что подпрямоугольник полностью определяется своими граничными линиями. После этого геометрическая задача превращается в произведение двух треугольных чисел, а оставшаяся вычислительная часть сводится к небольшому монотонному перебору.
В сетке \(m \times n\) есть \(m+1\) горизонтальных и \(n+1\) вертикальных линий. Чтобы задать подпрямоугольник, достаточно выбрать две различные горизонтальные и две различные вертикальные линии. Поэтому
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
Если обозначить \(k\)-е треугольное число через \(T_k=k(k+1)/2\), то формула принимает вид
$$R(m,n)=T_mT_n.$$
Именно произведение двух треугольных чисел и является центральным математическим объектом этой задачи.
Замкнутая форма получается и другим способом. Подпрямоугольник высоты \(h\) и ширины \(w\) можно разместить в \(m-h+1\) вертикальных и \(n-w+1\) горизонтальных положениях, поэтому
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
Поскольку горизонтальный и вертикальный выбор независимы, двойная сумма раскладывается:
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
Реализации используют именно эту факторизованную форму, поэтому каждый кандидат оценивается за постоянное время.
При \(m=3\) и \(n=2\) имеем
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
Значит, сетка \(3 \times 2\) содержит ровно 18 подпрямоугольников и имеет площадь \(6\). Это удобная проверка: её легко сделать вручную, и она совпадает с маленьким контрольным примером, используемым в решениях.
Функция подсчёта симметрична:
$$R(m,n)=R(n,m).$$
Поэтому достаточно рассматривать только пары с \(m \le n\). При фиксированном \(m\) значение строго растёт по \(n\):
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
Следовательно, как только в строке с фиксированным \(m\) значение превысило цель, дальнейшие \(n\) только ухудшают отклонение, и внутренний цикл можно завершить заранее. Реализации также используют щедрую верхнюю границу \(2000\); уже для полосы \(1 \times 2000\)
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000,$$
так что оптимум гарантированно лежит внутри этого окна поиска.
После сведения задачи к минимизации
$$\left|T_mT_n-2{,}000{,}000\right|$$
реализации находят пару
$$m=36,\qquad n=77.$$
Действительно,
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
то есть ошибка относительно цели равна всего \(2\). Следовательно, требуемая площадь равна
$$36 \cdot 77=2772.$$
Реализации на C++, Python и Java используют один и тот же прямой перебор. Сначала перебирается меньшая сторона, затем большая сторона начиная с этого же значения, чтобы не рассматривать отдельно и \((m,n)\), и \((n,m)\). Для каждой пары вычисляется \(R(m,n)=m(m+1)n(n+1)/4\), после чего абсолютное отклонение от цели сравнивается с текущим лучшим результатом.
Как только находится более близкая сетка, сохраняемая лучшая площадь обновляется. Поскольку при фиксированном \(m\) количество прямоугольников монотонно возрастает по \(n\), внутренний цикл обрывается после точки превышения цели, а не проходит по остатку строки. Одна из реализаций записывает это условие останова чуть более осторожно и дополнительно содержит маленькую проверку примера с возможностью менять цель, но математическое ядро во всех трёх языках одинаково.
Пусть \(B\) обозначает внешнюю границу перебора. Благодаря симметрии в худшем случае нужно проверить только пары \(1 \le m \le n \le B\), то есть не более
$$\frac{B(B+1)}{2}$$
кандидатов. При буквальном значении \(B=2000\) это \(2{,}001{,}000\) проверок ещё до учёта досрочных остановок.
Каждая проверка состоит лишь из константного числа целочисленных умножений и сравнений, поэтому время в худшем случае равно \(O(B^2)\), а память — \(O(1)\). На практике программа работает быстрее, потому что монотонный внутренний цикл обычно завершается заметно раньше верхней границы.
في شبكة أبعادها \(m \times n\)، نريد عد جميع المستطيلات الفرعية الموازية للمحاور. الهدف هو الاقتراب قدر الإمكان من العدد \(2{,}000{,}000\)، وليس من الضروري الوصول إليه بدقة تامة. أفضل شبكة هي \(36 \times 77\) (أو \(77 \times 36\))، لأنها تحتوي على \(1{,}999{,}998\) مستطيلًا فرعيًا، وبالتالي تكون مساحتها \(2772\).
الفكرة الحاسمة هي أن كل مستطيل فرعي يتحدد بالكامل بواسطة خطوط حدوده. بمجرد كتابة ذلك بصيغة توافقية، تتحول المسألة الهندسية إلى حاصل ضرب عددين مثلثيين، ثم تبقى بعد ذلك عملية بحث صغيرة ذات سلوك رتيب.
الشبكة \(m \times n\) تحتوي على \(m+1\) خطوط أفقية و\(n+1\) خطوط رأسية. ولتحديد مستطيل فرعي يكفي اختيار خطين أفقيين مختلفين وخطين رأسيين مختلفين. لذلك نحصل على
$$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$$
إذا رمزنا إلى العدد المثلثي رقم \(k\) بالرمز \(T_k=k(k+1)/2\)، تصبح الصيغة
$$R(m,n)=T_mT_n.$$
وهذا هو الكائن الرياضي المركزي في المسألة: كل شبكة مرشحة تقابل حاصل ضرب عددين مثلثيين.
يمكن الوصول إلى الصيغة المغلقة نفسها إذا عددنا بحسب الارتفاع والعرض. فالمستطيل الفرعي ذو الارتفاع \(h\) والعرض \(w\) يمكن وضعه في \(m-h+1\) مواضع رأسية و\(n-w+1\) مواضع أفقية، ومن ثم
$$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$$
وبما أن الاختيار الأفقي والرأسي مستقلان، فإن المجموع المزدوج ينفصل إلى
$$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$$
التنفيذات الثلاثة تستخدم هذه الصورة المفككة مباشرة، ولذلك يمكن تقييم كل شبكة مرشحة بزمن ثابت.
عندما \(m=3\) و\(n=2\)، نحصل على
$$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$$
إذن شبكة \(3 \times 2\) تحتوي بالضبط على 18 مستطيلًا فرعيًا ومساحتها \(6\). هذا المثال مهم لأنه قابل للتحقق يدويًا، كما أنه يطابق حالة الفحص الصغيرة الموجودة في الحلول.
دالة العد متماثلة:
$$R(m,n)=R(n,m).$$
ولهذا يكفي أن نفحص فقط الأزواج التي تحقق \(m \le n\). وإذا ثبتنا \(m\)، فإن العدد يزداد بازدياد \(n\) زيادة صارمة:
$$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$$
وبالتالي، بعد أن تتجاوز القيم الهدف في صف ثابت من البحث، فإن أي قيمة أكبر لـ \(n\) ستبتعد أكثر عن الهدف، ولذلك يمكن إنهاء الحلقة الداخلية مبكرًا. كما أن التنفيذات تستخدم حدًا أعلى مريحًا هو \(2000\). وحتى الشريط \(1 \times 2000\) وحده يحتوي على
$$R(1,2000)=T_1T_{2000}=2{,}001{,}000$$
مستطيلًا، لذا فإن الحل الأمثل يقع بأمان داخل نافذة البحث هذه.
بعد اختزال المسألة إلى تصغير
$$\left|T_mT_n-2{,}000{,}000\right|,$$
تجد التنفيذات أن أفضل زوج هو
$$m=36,\qquad n=77.$$
وذلك لأن
$$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$$
فتكون المسافة عن الهدف مساوية فقط لـ \(2\). ومن ثم فإن المساحة المطلوبة هي
$$36 \cdot 77=2772.$$
تستخدم تنفيذات C++ وPython وJava البحث المباشر نفسه. فهي تمر أولًا على الضلع الأصغر، ثم تمر على الضلع الأكبر ابتداءً من تلك القيمة، وبذلك لا تُفحص الحالتان \((m,n)\) و\((n,m)\) مرتين. ولكل زوج تُحسب القيمة \(R(m,n)=m(m+1)n(n+1)/4\) بزمن ثابت، ثم تُقارن المسافة المطلقة عن الهدف بأفضل مسافة مسجلة حتى تلك اللحظة.
كلما وُجدت شبكة أقرب إلى الهدف، تُحدَّث أفضل مساحة محفوظة. وبما أن عدد المستطيلات يزداد رتيبًا مع البعد الثاني عند تثبيت \(m\)، فإن الحلقة الداخلية تتوقف بعد نقطة التجاوز بدلًا من متابعة بقية الصف بلا فائدة. أحد التنفيذات يكتب شرط الإيقاف هذا بصورة أكثر تحفظًا قليلًا، ويضيف أيضًا فحصًا صغيرًا للمثال مع إمكانية تغيير الهدف، لكن الجوهر الرياضي واحد في اللغات الثلاث.
إذا كان الحد الخارجي هو \(B\)، فإن التماثل يختزل أسوأ حالة إلى الأزواج \(1 \le m \le n \le B\)، أي إلى عدد مرشحات لا يزيد على
$$\frac{B(B+1)}{2}.$$
وعند اختيار \(B=2000\) حرفيًا، فهذا يعني \(2{,}001{,}000\) تقييمًا على الأكثر قبل احتساب الإيقاف المبكر.
كل تقييم يتطلب عددًا ثابتًا فقط من عمليات الضرب والمقارنة الصحيحة، لذا فإن زمن التنفيذ في أسوأ حالة هو \(O(B^2)\)، بينما استهلاك الذاكرة هو \(O(1)\). وعمليًا يكون التنفيذ أسرع من هذا الحد لأن الحلقة الداخلية الرتيبة تنتهي غالبًا قبل الوصول إلى السقف الأعلى.