A hollow square lamina is a square frame: an outer square of side length \(o\) and a smaller inner square of side length \(i\), sharing the same center. Because the border must have integer thickness, the gap from the outer side to the inner side is even, so \(o-i \ge 2\) and \(o\) and \(i\) have the same parity.
The number of tiles used by such a lamina is the area difference
$$T=o^2-i^2.$$
For this problem the tile budget is \(L=1{,}000{,}000\). The task is to count how many distinct pairs \((o,i)\) satisfy the geometric constraints and \(T \le L\).
The implementations do not search over pictures. They count admissible integer pairs that represent square frames. The key facts are the difference-of-squares formula, the parity constraint, and the monotone behavior of the tile count when the inner square shrinks.
Once the outer side \(o\) and inner side \(i\) are fixed, the lamina is completely determined. The centered-border condition implies
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
The area removed from the outer square is exactly the inner square, so the tile count is
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
This factorization is useful because it makes the parity restriction visible: \(o-i\) measures twice the border thickness, while \(o+i\) records the corresponding average scale.
Let
$$k=\frac{o-i}{2},$$
so \(k \ge 1\) is the thickness of the square border measured in tiles. Then
$$i=o-2k,$$
and the positivity of the inner square gives
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
Substituting \(i=o-2k\) into the tile formula yields
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
So the whole counting problem can be written as
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
The code does not solve this inequality in closed form for each \(o\); instead it walks through the valid \(k\)-values in increasing order by decreasing the inner side in steps of 2.
For a fixed outer side \(o\), the smallest possible border is \(k=1\), equivalently \(i=o-2\). That gives the minimum number of tiles for that outer square:
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
This simple expression explains the outer-loop stopping rule. If even the thinnest lamina with outer side \(o\) already exceeds the limit, then every thicker lamina with the same outer side also exceeds the limit. Therefore the outer loop only needs to continue while
$$4o-4 \le L.$$
For \(L=1{,}000{,}000\), this means
$$o \le \frac{L}{4}+1=250001.$$
For a fixed outer side, the implementations try inner sides in the order
$$i=o-2,\ o-4,\ o-6,\ \dots$$
which is the same as trying \(k=1,2,3,\dots\). The crucial point is that the tile count grows strictly in that order. Using the inner-side form,
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
and this is positive for every admissible \(i>1\). In the thickness form, the same fact is
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
which stays positive throughout the allowed range \(k \lt (o-1)/2\).
That monotonicity is the invariant that justifies the break in the code: once one candidate exceeds the tile limit, every later candidate for the same outer side will also exceed it.
Take a smaller budget, say \(L=50\), and fix the outer side at \(o=8\). The admissible inner sides have the same parity as 8, so they are \(i=6,4,2\).
The corresponding tile counts are
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
So the first two laminae are valid, while the third is not. Because the tile counts increase as the inner side decreases, the moment 60 appears the search for \(o=8\) can stop immediately. This is exactly the behavior implemented by the nested loops.
The C++, Python, and Java implementations all follow the same counting strategy. They sweep the outer side length upward starting from \(o=3\), because \(3\times3\) with a \(1\times1\) hole is the smallest nontrivial square lamina. The outer sweep ends when the minimal tile count \(4o-4\) exceeds the budget.
For each fixed outer side, the implementation starts with the largest possible inner side, \(i=o-2\), and then decreases \(i\) by 2 so that parity is preserved automatically. Each pair \((o,i)\) corresponds to one distinct lamina, and the implementation computes \(o^2-i^2\). If that value is within the limit, the count increases by 1. If it exceeds the limit, the inner loop terminates immediately because all later inner sides would use even more tiles.
The three language versions differ only in presentation details. They implement the same mathematics, the same loop order, and the same early-exit rule. The C++ version additionally includes a small checkpoint confirming that a budget of 100 tiles produces 41 laminae, which matches the example given in the problem statement.
The outer loop runs for \(o=3,4,\dots,\lfloor L/4\rfloor+1\), so there are \(O(L)\) outer iterations as a function of the tile limit \(L\).
For a fixed \(o\), the inner loop explores increasing border thickness \(k\). Since \(k \le \lfloor(o-1)/2\rfloor\) and \(4k(o-k)\le L\), while \(k \le o/2\) we also have \(o-k \ge o/2\), hence
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
Therefore the number of successful inner iterations for a given outer side is
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$$
Summing over all outer sides gives \(O(L\log L)\) total work. Memory usage is \(O(1)\), because the implementation stores only a few integers and the running count.
Eine hohle quadratische Lamina ist ein quadratischer Rahmen: ein äußeres Quadrat mit Seitenlänge \(o\) und ein inneres Quadrat mit Seitenlänge \(i\), beide mit demselben Mittelpunkt. Weil die Randdicke ganzzahlig sein muss, ist der Unterschied der Seitenlängen gerade. Also gilt \(o-i \ge 2\) und \(o\) und \(i\) haben dieselbe Parität.
Die Zahl der verwendeten Plättchen ist die Flächendifferenz
$$T=o^2-i^2.$$
Hier ist das Limit \(L=1{,}000{,}000\). Gesucht ist also die Anzahl aller zulässigen Paare \((o,i)\), für die \(T \le L\) gilt.
Die Implementierungen zählen keine Zeichnungen, sondern ganzzahlige Parameterpaare. Die gesamte Lösung beruht auf drei Beobachtungen: der Darstellung als Quadratedifferenz, der Paritätsbedingung und der Monotonie der Kachelzahl, wenn das innere Quadrat kleiner wird.
Ist die äußere Seitenlänge \(o\) und die innere Seitenlänge \(i\) festgelegt, dann ist die Lamina eindeutig bestimmt. Wegen des zentrierten Randes gilt
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
Die Kachelzahl ist genau die Differenz der beiden Quadratflächen:
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
Diese Faktorisierung ist nicht nur algebraisch hübsch. Sie zeigt unmittelbar, dass \(o-i\) doppelt der Randdicke entspricht.
Setze
$$k=\frac{o-i}{2},$$
wobei \(k \ge 1\) die Dicke des quadratischen Rahmens in Kacheln ist. Dann folgt
$$i=o-2k,$$
und weil das innere Quadrat positiv bleiben muss, erhält man
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
Einsetzen in die Flächendifferenz liefert
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
Damit kann man die gesuchte Anzahl als Summe schreiben:
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
Der Code löst diese Ungleichung nicht direkt, sondern zählt die zulässigen Werte durch eine monotone Schleife.
Für festes \(o\) entsteht die dünnste und damit kachelärmste Lamina bei \(k=1\), also \(i=o-2\). Das ergibt
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Genau daraus folgt die Abbruchbedingung der äußeren Schleife. Wenn bereits diese Minimalzahl das Limit übersteigt, dann kann für dieses und jedes größere \(o\) keine gültige Lamina mehr existieren. Deshalb genügt
$$4o-4 \le L.$$
Für \(L=1{,}000{,}000\) heißt das konkret \(o \le 250001\).
Bei festem \(o\) probieren die Implementierungen die inneren Seiten in der Reihenfolge
$$i=o-2,\ o-4,\ o-6,\ \dots$$
also äquivalent \(k=1,2,3,\dots\). Die Kachelzahl wächst dabei streng. Direkt mit den inneren Seiten gilt
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
und das ist für jedes zulässige \(i>1\) positiv. In der \(k\)-Schreibweise lautet dieselbe Aussage
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
was im gesamten gültigen Bereich positiv bleibt.
Diese Monotonie ist das entscheidende Invariante der Implementierung: Sobald eine Kandidatenlamina das Limit überschreitet, werden alle späteren Kandidaten für dasselbe Außenquadrat ebenfalls zu groß sein, und die Schleife kann beendet werden.
Nehmen wir ein kleineres Limit \(L=50\) und fixieren \(o=8\). Wegen der Parität kommen nur \(i=6,4,2\) infrage.
Die Kachelzahlen sind
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
Die ersten beiden Laminae sind also gültig, die dritte nicht mehr. Weil die Werte streng wachsen, ist nach 60 klar, dass für \(o=8\) nichts mehr zu zählen ist. Genau so nutzt der Code den frühen Abbruch.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Zählidee. Die äußere Schleife erhöht die Seitenlänge des äußeren Quadrats ab \(o=3\), denn \(3\times3\) mit einem \(1\times1\)-Loch ist die kleinste nichttriviale Lamina. Sie endet, sobald die dünnste mögliche Lamina \(4o-4\) das Kachellimit überschreitet.
Für jedes feste \(o\) startet die innere Schleife mit dem größtmöglichen inneren Quadrat \(i=o-2\) und verkleinert \(i\) jeweils um 2. So bleibt die Parität automatisch korrekt. Für jedes Paar \((o,i)\) berechnet die Implementierung \(o^2-i^2\). Liegt der Wert innerhalb des Limits, wird der Zähler erhöht. Liegt er darüber, wird die innere Schleife sofort beendet, weil alle folgenden inneren Seiten noch mehr Kacheln benötigen.
Die drei Sprachversionen unterscheiden sich nur in der äußeren Form. Mathematisch verwenden sie denselben Suchraum, dieselbe Abbruchlogik und dieselbe Zählung. Die C++-Variante enthält zusätzlich einen kleinen Prüfschritt, der bestätigt, dass bei einem Limit von 100 genau 41 Laminae entstehen.
Die äußere Schleife durchläuft \(o=3,4,\dots,\lfloor L/4\rfloor+1\); das sind \(O(L)\) Iterationen in Abhängigkeit vom Kachellimit \(L\).
Für festes \(o\) ist die Anzahl erfolgreicher innerer Schritte durch zwei Größen beschränkt: durch \(k \le \lfloor(o-1)/2\rfloor\) und durch die Ungleichung \(4k(o-k)\le L\). Da im gültigen Bereich \(k \le o/2\) stets \(o-k \ge o/2\) gilt, folgt
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
Somit kostet ein festes \(o\)
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right)$$
innere Iterationen. Über alle äußeren Seiten summiert ergibt das insgesamt \(O(L\log L)\) Zeit. Der Speicherbedarf ist \(O(1)\), weil nur einige ganzzahlige Variablen und der laufende Zähler gehalten werden.
Boşluklu kare lamina, aynı merkezli iki kareden oluşan bir çerçevedir: dış karenin kenarı \(o\), iç karenin kenarı \(i\). Çerçeve kalınlığı tam sayı olmalı, bu yüzden kenar farkı çift olmalıdır. Dolayısıyla \(o-i \ge 2\) ve \(o\) ile \(i\) aynı paritye sahiptir.
Kullanılan karo sayısı alan farkıdır:
$$T=o^2-i^2.$$
Bu problemde üst sınır \(L=1{,}000{,}000\) karodur. Amaç, geometrik koşulları sağlayan ve \(T \le L\) olan tüm farklı \((o,i)\) çiftlerini saymaktır.
Uygulamalar şekil çizmek yerine tamsayı çiftlerini sayar. Temel fikirler şunlardır: karo sayısının iki kare farkı olması, iç ve dış kenarların aynı parityi paylaşması ve iç kare küçüldükçe karo sayısının tek yönde artması.
Dış kenar \(o\) ve iç kenar \(i\) verildiğinde lamina tamamen belirlenir. Merkezlerin aynı olması ve kenar kalınlığının tam sayı olması nedeniyle
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
Karo sayısı dış kare alanından iç kare alanının çıkarılmasıyla bulunur:
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
Bu çarpanlara ayrılmış biçim, \(o-i\) ifadesinin aslında sınır kalınlığının iki katı olduğunu açıkça gösterir.
Şimdi
$$k=\frac{o-i}{2}$$
olsun. Burada \(k \ge 1\), çerçevenin karo cinsinden kalınlığıdır. O zaman
$$i=o-2k,$$
ve iç karenin pozitif kalması için
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor$$
olmalıdır. Bunu karo sayısına yerleştirince
$$T(o,k)=o^2-(o-2k)^2=4k(o-k)$$
elde edilir. Böylece toplam sayı şu biçimde yazılabilir:
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
Kod bu eşitsizliği kapalı formda çözmez; bunun yerine uygun \(k\) değerlerini artan sırada dener.
Sabit bir \(o\) için en ince çerçeve \(k=1\), yani \(i=o-2\) durumudur. O halde bu dış kare için gereken en az karo sayısı
$$T_{\min}(o)=o^2-(o-2)^2=4o-4$$
olur. Dış döngünün neden burada durduğunu açıklayan ifade budur. Eğer en ince olası lamina bile limiti aşıyorsa, aynı dış kenar için daha kalın bütün laminalar da limiti aşacaktır. Bu yüzden dış döngü yalnızca
$$4o-4 \le L$$
koşulu sağlanırken sürdürülür. \(L=1{,}000{,}000\) için bu, \(o \le 250001\) demektir.
Sabit bir dış kenarda iç kenarlar şu sırayla denenir:
$$i=o-2,\ o-4,\ o-6,\ \dots$$
Bu, \(k=1,2,3,\dots\) sırasına eşdeğerdir. Önemli nokta, karo sayısının bu sırada sıkı biçimde artmasıdır. İç kenar diliyle
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
ve bu ifade her geçerli \(i>1\) için pozitiftir. Kalınlık değişkeniyle aynı gerçek
$$T(o,k+1)-T(o,k)=4(o-2k-1)$$
şeklinde yazılır ve geçerli aralık boyunca pozitiftir.
Bu monotonluk, kodun kullandığı temel değişmezdir: bir aday limitin üstüne çıktığı anda, aynı dış kenar için ondan sonra gelecek bütün adayların da daha büyük olacağı garanti edilir. Bu yüzden döngü güvenle kesilir.
Daha küçük bir bütçe alalım: \(L=50\). Dış kenarı \(o=8\) olarak sabitleyelim. 8 ile aynı paritye sahip iç kenarlar \(i=6,4,2\) olur.
Bunların karo sayıları
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60$$
şeklindedir. İlk iki lamina geçerlidir, üçüncüsü değildir. Ayrıca değerler artarak gittiği için 60 görüldüğü anda \(o=8\) için başka bir geçerli aday kalmadığı anlaşılır. İç döngüdeki erken çıkış tam olarak bunu kullanır.
C++, Python ve Java uygulamalarının üçü de aynı sayma düzenini uygular. Dış kenar uzunluğu \(o=3\) ile başlar; çünkü \(3\times3\) dış kare ve \(1\times1\) iç boşluk en küçük anlamlı laminadır. Dış döngü, \(4o-4\) değeri limiti aşınca sona erer.
Her sabit \(o\) için iç döngü en büyük olası iç kare olan \(i=o-2\) ile başlar ve \(i\) değerini her adımda 2 azaltır. Böylece parity koşulu otomatik olarak korunur. Her \((o,i)\) çifti için \(o^2-i^2\) hesaplanır. Sonuç limit içindeyse sayaç bir artırılır; değilse iç döngü hemen sonlandırılır, çünkü daha küçük tüm iç kareler daha fazla karo gerektirecektir.
Diller arasındaki fark yalnızca sunum düzeyindedir. Matematik, dolaşılan durum uzayı ve erken çıkış kuralı aynıdır. C++ sürümü ayrıca küçük bir doğrulama adımı içerir ve 100 karo sınırı için 41 lamina elde edilmesini kontrol eder.
Dış döngü \(o=3,4,\dots,\lfloor L/4\rfloor+1\) değerlerini gezer; dolayısıyla karo limiti \(L\) cinsinden \(O(L)\) dış iterasyon vardır.
Sabit \(o\) için iç döngünün başarılı adım sayısı iki kısıtla belirlenir: \(k \le \lfloor(o-1)/2\rfloor\) ve \(4k(o-k)\le L\). Geçerli bölgede \(k \le o/2\) olduğundan \(o-k \ge o/2\) yazabiliriz. Buradan
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}$$
çıkar. O halde sabit bir \(o\) için iş miktarı
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right)$$
olur. Tüm dış kenarlar üzerinde toplandığında toplam süre \(O(L\log L)\) düzeyindedir. Bellek kullanımı \(O(1)\)'dir; yalnızca birkaç tamsayı ve toplam sayaç tutulur.
Una lamina cuadrada hueca es un marco formado por dos cuadrados concéntricos: uno exterior de lado \(o\) y otro interior de lado \(i\). Como el grosor del borde debe ser entero, la diferencia entre los lados es par. Por tanto, \(o-i \ge 2\) y \(o\) e \(i\) tienen la misma paridad.
El número de baldosas utilizadas es la diferencia de áreas
$$T=o^2-i^2.$$
En este problema el límite es \(L=1{,}000{,}000\). Hay que contar cuántos pares \((o,i)\) cumplen las restricciones geométricas y además satisfacen \(T \le L\).
Las implementaciones no manipulan dibujos, sino parámetros enteros. Toda la solución se apoya en la identidad de diferencia de cuadrados, en la restricción de paridad y en que, para un lado exterior fijo, el número de baldosas crece de manera monótona cuando el cuadrado interior se hace más pequeño.
Si fijamos el lado exterior \(o\) y el lado interior \(i\), la lamina queda determinada por completo. Las condiciones de estar centrada y tener grosor entero implican
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
El número de baldosas es exactamente
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
La factorización es útil porque separa el grosor del borde, contenido en \(o-i\), de la escala total, contenida en \(o+i\).
Definamos
$$k=\frac{o-i}{2},$$
donde \(k \ge 1\) es el grosor del marco en baldosas. Entonces
$$i=o-2k,$$
y, para que el cuadrado interior siga existiendo, se necesita
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
Al sustituir en la fórmula del área obtenemos
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
Por tanto, el conteo total puede escribirse como
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
El código no resuelve esta desigualdad de forma cerrada para cada \(o\); la explora directamente en el orden correcto.
Si \(o\) es fijo, la lamina más delgada corresponde a \(k=1\), es decir, \(i=o-2\). Su coste en baldosas es
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Esto explica la condición de parada del bucle externo. Si incluso la lamina más fina con ese lado exterior supera el límite, entonces todas las más gruesas también lo superan. Por eso basta iterar mientras
$$4o-4 \le L.$$
Con \(L=1{,}000{,}000\), esto da \(o \le 250001\).
Para un \(o\) fijo, las implementaciones prueban los lados interiores en el orden
$$i=o-2,\ o-4,\ o-6,\ \dots$$
equivalente a \(k=1,2,3,\dots\). El punto crucial es que el número de baldosas crece estrictamente en ese orden. Usando la variable \(i\),
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
y eso es positivo para todo \(i>1\). En términos de \(k\), la misma propiedad es
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
que sigue siendo positiva dentro del rango permitido.
Esa monotonía es la invariante que justifica el corte temprano: en cuanto una opción sobrepasa el presupuesto, ninguna opción posterior con el mismo lado exterior podrá volver a ser válida.
Tomemos un presupuesto menor, \(L=50\), y fijemos \(o=8\). Los lados interiores válidos, por paridad, son \(i=6,4,2\).
Los números de baldosas son
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
Las dos primeras configuraciones cuentan y la tercera no. Además, como los valores van creciendo, cuando aparece 60 ya sabemos que la exploración para \(o=8\) debe terminar. Esa es exactamente la poda que aplica el programa.
Las implementaciones en C++, Python y Java siguen la misma estrategia. Recorren el lado exterior \(o\) a partir de 3, porque la lamina más pequeña usa un cuadrado exterior \(3\times3\) y un hueco interior \(1\times1\). El recorrido exterior termina cuando el coste mínimo \(4o-4\) rebasa el límite.
Para cada \(o\), la implementación empieza con el mayor lado interior posible, \(i=o-2\), y luego reduce \(i\) de dos en dos. Así se mantiene automáticamente la paridad correcta. Para cada par \((o,i)\), se calcula \(o^2-i^2\). Si el resultado no supera el límite, se incrementa el contador. Si lo supera, el bucle interior se rompe enseguida, porque cualquier lado interior aún menor produciría más baldosas.
Las tres versiones difieren solo en detalles de presentación. La matemática, el orden de enumeración y la poda temprana son idénticos. La versión en C++ añade además una verificación pequeña: con un límite de 100 baldosas deben contarse 41 laminas.
El bucle exterior recorre \(o=3,4,\dots,\lfloor L/4\rfloor+1\), de modo que hay \(O(L)\) iteraciones exteriores en función del límite \(L\).
Para un \(o\) fijo, el número de iteraciones útiles del bucle interior está limitado por \(k \le \lfloor(o-1)/2\rfloor\) y por la desigualdad \(4k(o-k)\le L\). Como en el rango válido se cumple \(k \le o/2\), también se tiene \(o-k \ge o/2\), y por tanto
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
Así, el trabajo para un lado exterior fijo es
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$$
Al sumar sobre todos los valores de \(o\), el tiempo total es \(O(L\log L)\). El consumo de memoria es \(O(1)\), ya que solo se guardan unos pocos enteros y el contador acumulado.
空心正方形层板可以看成一个正方形边框：外层正方形边长为 \(o\)，内层挖空的正方形边长为 \(i\)，两者同心。因为边框厚度必须是整数个瓷砖，所以外边长与内边长之差必须是偶数。因此有 \(o-i \ge 2\)，并且 \(o\) 与 \(i\) 具有相同奇偶性。
所用瓷砖数就是面积之差：
$$T=o^2-i^2.$$
本题给出的上限是 \(L=1{,}000{,}000\)。因此我们要统计的，是所有满足几何条件并且 \(T \le L\) 的不同整数对 \((o,i)\) 的个数。
实现并不是在枚举图形，而是在枚举能够唯一确定图形的整数参数。整个解法依赖三个核心事实：瓷砖数是两个平方的差，内外边长必须同奇同偶，以及在外边长固定时，随着内方孔变小，所需瓷砖数会严格增大。
一旦给定外边长 \(o\) 和内边长 \(i\)，这个空心正方形层板就被唯一确定。由于它们同心且边框厚度必须是整数，所以必须满足
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
对应的瓷砖数正好是外正方形减去内正方形的面积：
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
这个分解非常重要，因为它把“边框厚度”与“整体尺寸”分开了：\(o-i\) 反映边框有多厚，\(o+i\) 反映整个图形有多大。
令
$$k=\frac{o-i}{2},$$
其中 \(k \ge 1\) 表示边框厚度有多少层瓷砖。于是
$$i=o-2k,$$
而内层正方形仍然必须保持正边长，所以
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
把这个式子代回去，可得
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
因此，题目本质上是在计算
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
代码并没有对每个 \(o\) 直接解出这个不等式的闭式，而是按照一个单调的顺序去枚举合法的 \(k\)。
当外边长 \(o\) 固定时，最薄的边框对应 \(k=1\)，也就是 \(i=o-2\)。这时所需瓷砖数最少：
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
这正是外层循环停止条件的来源。如果连最薄的一圈都已经超过上限，那么同一个外边长下更厚的边框只会用掉更多瓷砖，因此根本不必继续尝试。于是外层循环只需要在
$$4o-4 \le L$$
成立时继续。对于 \(L=1{,}000{,}000\)，这意味着
$$o \le \frac{L}{4}+1=250001.$$
在固定外边长 \(o\) 的情况下，程序按照
$$i=o-2,\ o-4,\ o-6,\ \dots$$
这样的顺序尝试内边长。也就是说，它等价于按 \(k=1,2,3,\dots\) 的顺序增加边框厚度。关键在于：瓷砖数会沿着这个顺序严格上升。直接用 \(i\) 表示时，
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
只要 \(i>1\)，这个差就为正。若改用厚度参数 \(k\)，同样的结论写成
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
在合法范围内它同样保持为正。
这就是代码中提前 break 的数学依据：一旦某个内边长已经让瓷砖数超出上限，那么继续减小内边长只会让瓷砖数更大，所以当前外边长下不可能再出现新的合法层板。
取一个较小的预算 \(L=50\)，并固定外边长 \(o=8\)。因为奇偶性必须一致，可选的内边长只有 \(i=6,4,2\)。
对应的瓷砖数分别为
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
所以前两种层板有效，第三种无效。更重要的是，这三个数是递增的，因此一旦出现 60，就已经可以断定对 \(o=8\) 而言后面不再有合法解。程序正是利用这一点来减少搜索量。
C++、Python 和 Java 三份实现采用完全相同的枚举思路。外层从 \(o=3\) 开始向上扫描，因为最小的非平凡空心正方形层板就是外边长 3、内边长 1 的情形。只要最薄层板所需的 \(4o-4\) 仍不超过预算，外层循环就继续。
对每一个固定的 \(o\)，实现都会先取最大的合法内边长 \(i=o-2\)，然后每次把 \(i\) 减少 2。这样做自动保证了奇偶性正确，不需要额外判定。每得到一个 \((o,i)\) 对，就计算 \(o^2-i^2\)。如果结果不超过上限，计数加 1；如果结果超过上限，就立即结束当前内层循环，因为后面的候选只会更大。
三种语言的差别只在代码书写形式上，数学逻辑完全一致：同样的参数化方式、同样的循环顺序、同样的提前终止规则。C++ 版本还额外包含了一个小检查，用题目中的示例验证当预算为 100 时答案确实是 41。
外层循环遍历 \(o=3,4,\dots,\lfloor L/4\rfloor+1\)，因此相对于瓷砖上限 \(L\) 来说，外层迭代次数是 \(O(L)\)。
对固定的 \(o\)，内层循环的成功次数同时受到两类限制：一方面 \(k \le \lfloor(o-1)/2\rfloor\)，另一方面必须满足 \(4k(o-k)\le L\)。在合法范围内有 \(k \le o/2\)，因此 \(o-k \ge o/2\)，从而
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
于是，固定一个外边长时，内层工作量可以写成
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$$
把这个上界对所有 \(o\) 累加，总时间复杂度就是 \(O(L\log L)\)。空间复杂度为 \(O(1)\)，因为实现只维护少量整数变量和累计计数，不需要保存任何大型表结构。
Полая квадратная ламина представляет собой квадратную рамку: внешний квадрат со стороной \(o\) и внутренний квадрат со стороной \(i\), имеющие общий центр. Поскольку толщина рамки должна быть целым числом плиток, разность сторон обязана быть чётной. Значит, выполняется \(o-i \ge 2\), а числа \(o\) и \(i\) имеют одинаковую чётность.
Число использованных плиток равно разности площадей:
$$T=o^2-i^2.$$
В задаче задан предел \(L=1{,}000{,}000\). Нужно подсчитать количество различных пар \((o,i)\), удовлетворяющих геометрическим условиям и неравенству \(T \le L\).
Реализации не работают с картинками напрямую, а перебирают целочисленные параметры, которые однозначно задают рамку. Основа решения состоит из трёх частей: формула разности квадратов, условие совпадения чётности и монотонный рост числа плиток при уменьшении внутреннего квадрата.
Если известны внешний размер \(o\) и внутренний размер \(i\), ламина определена полностью. Условие соосности и целочисленной толщины даёт
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
Число плиток равно
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
Эта факторизация полезна не только сама по себе. Она подчёркивает, что \(o-i\) связано с толщиной рамки, а \(o+i\) описывает общий масштаб фигуры.
Положим
$$k=\frac{o-i}{2},$$
где \(k \ge 1\) обозначает толщину рамки в плитках. Тогда
$$i=o-2k,$$
а положительность внутреннего квадрата требует
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
Подстановка в формулу площади даёт
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
Следовательно, искомое количество можно записать как
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
Код не решает это неравенство в закрытом виде для каждого \(o\), а просто перебирает допустимые значения в правильном порядке.
Если сторона внешнего квадрата \(o\) фиксирована, минимальное число плиток получается при самой тонкой рамке, то есть при \(k=1\), или \(i=o-2\). Тогда
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
Именно эта формула объясняет условие остановки внешнего цикла. Если даже самая тонкая рамка с данным внешним размером уже превышает лимит, то все более толстые рамки тем более не подходят. Поэтому внешний цикл продолжается только пока
$$4o-4 \le L.$$
При \(L=1{,}000{,}000\) это означает \(o \le 250001\).
Для фиксированного \(o\) реализации перебирают внутреннюю сторону в порядке
$$i=o-2,\ o-4,\ o-6,\ \dots$$
то есть эквивалентно перебирают \(k=1,2,3,\dots\). Важный факт состоит в том, что число плиток в этом порядке строго возрастает. В записи через \(i\)
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
и это положительно для любого допустимого \(i>1\). В параметре толщины это же свойство выглядит так:
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
и оно остаётся положительным на всём допустимом диапазоне.
Эта монотонность и есть главный инвариант цикла: как только очередной кандидат превысил лимит, все последующие кандидаты с тем же внешним квадратом будут только хуже, поэтому внутренний перебор можно немедленно завершить.
Рассмотрим меньший бюджет \(L=50\) и зафиксируем \(o=8\). Из-за условия чётности возможны только \(i=6,4,2\).
Соответствующие числа плиток равны
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
Первые две рамки допустимы, третья уже нет. Поскольку значения возрастают, появление 60 сразу означает, что для \(o=8\) продолжать больше не нужно. Именно так работает ранний выход в реализации.
Реализации на C++, Python и Java используют один и тот же порядок перебора. Внешняя сторона \(o\) начинается с 3, потому что самая маленькая нетривиальная ламина имеет внешний квадрат \(3\times3\) и внутреннее отверстие \(1\times1\). Внешний цикл завершается, когда минимальная возможная стоимость \(4o-4\) становится больше лимита.
Для каждого фиксированного \(o\) внутренний цикл стартует с наибольшего допустимого внутреннего квадрата \(i=o-2\), а затем уменьшает \(i\) на 2. Так автоматически сохраняется правильная чётность. Для каждой пары \((o,i)\) вычисляется \(o^2-i^2\). Если значение не превышает лимит, счётчик увеличивается. Если превышает, цикл немедленно прерывается, потому что дальнейшие варианты будут использовать ещё больше плиток.
Различия между тремя версиями только синтаксические. Математика, порядок обхода и правило ранней остановки полностью совпадают. Версия на C++ вдобавок содержит небольшую проверку: для лимита 100 правильное количество равно 41.
Внешний цикл проходит по значениям \(o=3,4,\dots,\lfloor L/4\rfloor+1\), то есть даёт \(O(L)\) итераций как функцию от лимита \(L\).
Для фиксированного \(o\) число полезных шагов внутреннего цикла ограничено двумя условиями: \(k \le \lfloor(o-1)/2\rfloor\) и \(4k(o-k)\le L\). Так как в допустимом диапазоне \(k \le o/2\), имеем \(o-k \ge o/2\), откуда следует
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
Значит, работа для одного внешнего размера оценивается как
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$$
После суммирования по всем \(o\) получаем суммарную временную сложность \(O(L\log L)\). Память имеет порядок \(O(1)\), потому что хранятся только несколько целых переменных и накопленный счётчик.
اللامينا المربعة المجوفة هي إطار مربّع يتكوّن من مربع خارجي طول ضلعه \(o\) ومربع داخلي طول ضلعه \(i\)، وكلاهما لهما المركز نفسه. وبما أن سماكة الإطار يجب أن تكون عددًا صحيحًا من البلاطات، فإن الفرق بين الضلعين لا بد أن يكون زوجيًا. لذلك لدينا \(o-i \ge 2\)، كما أن \(o\) و\(i\) لهما الزوجية نفسها.
عدد البلاطات المستعملة يساوي فرق المساحتين:
$$T=o^2-i^2.$$
في هذه المسألة الحد الأقصى هو \(L=1{,}000{,}000\). والمطلوب هو عدّ جميع الأزواج المختلفة \((o,i)\) التي تحقق الشروط الهندسية وكذلك \(T \le L\).
التنفيذ لا يعدّ الأشكال مباشرة، بل يعدّ أزواجًا صحيحة تمثل هذه الأشكال تمثيلًا وحيدًا. الفكرة كلها تعتمد على ثلاثة أمور: صيغة فرق مربعين، شرط تساوي الزوجية بين الضلعين، وأن عدد البلاطات يزداد بشكل رتيب عندما نصغّر المربع الداخلي مع تثبيت المربع الخارجي.
إذا عرفنا طول الضلع الخارجي \(o\) وطول الضلع الداخلي \(i\)، فإن اللامينا تتحدد بالكامل. وبسبب تمركز المربعين وضرورة أن تكون السماكة عددًا صحيحًا، نحصل على الشروط
$$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$$
وعندئذ يكون عدد البلاطات
$$T(o,i)=o^2-i^2=(o-i)(o+i).$$
هذه الصيغة المفككة مفيدة لأنها تُظهر أن \(o-i\) يمثّل ضعف سماكة الإطار، بينما \(o+i\) يعكس الحجم الكلي للشكل.
لنضع
$$k=\frac{o-i}{2},$$
حيث إن \(k \ge 1\) هو عدد طبقات البلاطات في الإطار. عندئذ
$$i=o-2k,$$
ومن أجل أن يبقى المربع الداخلي ذا ضلع موجب، يجب أن يكون
$$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$$
بالتعويض في صيغة المساحة نحصل على
$$T(o,k)=o^2-(o-2k)^2=4k(o-k).$$
إذًا يمكن كتابة العدد الكلي المطلوب بالشكل
$$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$$
لكن الشيفرة لا تحل هذه المتراجحة بصيغة مغلقة لكل \(o\)، بل تعدّ القيم المسموح بها بترتيب يضمن إمكانية الإيقاف المبكر.
عندما نثبت \(o\)، فإن أنحف إطار ممكن يقابل \(k=1\)، أي \(i=o-2\). وفي هذه الحالة يكون أقل عدد من البلاطات هو
$$T_{\min}(o)=o^2-(o-2)^2=4o-4.$$
ومن هنا تأتي قاعدة التوقف في الحلقة الخارجية. فإذا كانت حتى اللامينا الأرفع ذات الضلع الخارجي \(o\) تتجاوز الحد، فإن أي لامينا أكثر سماكة بالضلع الخارجي نفسه ستتجاوزه كذلك. لذلك تستمر الحلقة الخارجية فقط ما دام
$$4o-4 \le L.$$
وعند \(L=1{,}000{,}000\) يعني هذا أن \(o \le 250001\).
عند تثبيت \(o\)، تُجرَّب الأضلاع الداخلية بالترتيب
$$i=o-2,\ o-4,\ o-6,\ \dots$$
وهو نفسه ترتيب \(k=1,2,3,\dots\). النقطة الحاسمة هي أن عدد البلاطات يزداد زيادة صارمة مع هذا الترتيب. باستخدام \(i\) مباشرة نحصل على
$$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4i-4,$$
وهذا موجب لكل \(i>1\). وبصياغة السماكة نفسها تصبح الحقيقة
$$T(o,k+1)-T(o,k)=4(o-2k-1),$$
وهي موجبة على المجال المسموح.
هذا التزايد الرتيب هو المبدأ الذي تعتمد عليه الشيفرة: بمجرد أن يتجاوز أحد المرشحين الحد الأقصى، يصبح من المؤكد أن جميع المرشحين اللاحقين للضلع الخارجي نفسه سيتجاوزونه أيضًا، ولذلك يمكن كسر الحلقة الداخلية فورًا.
لنأخذ ميزانية أصغر هي \(L=50\)، ولنثبت الضلع الخارجي عند \(o=8\). بسبب شرط الزوجية تكون القيم الداخلية الممكنة هي \(i=6,4,2\).
أعداد البلاطات المقابلة هي
$$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$$
إذًا الحالتان الأوليان صالحتان، أما الثالثة فلا. والأهم أن القيم تصاعدية، لذلك عندما نصل إلى 60 نعرف مباشرة أنه لا توجد حالة أخرى صالحة عند \(o=8\). هذا بالضبط هو سبب الإيقاف المبكر في التنفيذ.
تنفّذ نسخ C++ وPython وJava الخطة نفسها تمامًا. تبدأ الحلقة الخارجية من \(o=3\)، لأن أصغر لامينا غير تافهة هي مربع خارجي \(3\times3\) مع ثقب داخلي \(1\times1\). وتستمر الحلقة ما دام أقل عدد ممكن من البلاطات، وهو \(4o-4\)، لا يتجاوز الحد.
لكل قيمة ثابتة من \(o\)، تبدأ الشيفرة بأكبر ضلع داخلي ممكن \(i=o-2\)، ثم تُنقص \(i\) بمقدار 2 في كل مرة. بهذه الطريقة يتم الحفاظ على شرط الزوجية تلقائيًا من غير فحص إضافي. ولكل زوج \((o,i)\) تُحسب القيمة \(o^2-i^2\). إذا كانت ضمن الحد يزداد العداد بمقدار 1، وإذا تجاوزته تُكسر الحلقة الداخلية مباشرة لأن أي ضلع داخلي أصغر سيستهلك عددًا أكبر من البلاطات.
الاختلاف بين اللغات الثلاث شكلي فقط. الرياضيات، وترتيب التعداد، وقاعدة الإيقاف المبكر كلها واحدة. كما أن نسخة C++ تحتوي على فحص صغير يؤكد أن الحد 100 يعطي 41 لامينا، كما في المثال الوارد في نص المسألة.
تمر الحلقة الخارجية على القيم \(o=3,4,\dots,\lfloor L/4\rfloor+1\)، ولذلك فإن عدد تكراراتها هو \(O(L)\) بدلالة حد البلاطات \(L\).
أما عند تثبيت \(o\)، فإن عدد خطوات الحلقة الداخلية الناجحة تحده حقيقتان: \(k \le \lfloor(o-1)/2\rfloor\) و\(4k(o-k)\le L\). وبما أن \(k \le o/2\) على المجال المسموح، فإن \(o-k \ge o/2\)، ومن ثم
$$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$$
إذًا الشغل المطلوب لكل ضلع خارجي ثابت يساوي
$$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$$
وبجمع ذلك على جميع قيم \(o\) نحصل على زمن كلي من رتبة \(O(L\log L)\). أما الذاكرة فهي \(O(1)\)، لأن التنفيذ لا يخزّن سوى عدد صغير من القيم الصحيحة والعداد التراكمي.