Take a cuboid with integer side lengths \(m \ge b \ge c \ge 1\). A spider starts at one corner and wants to reach the opposite corner while staying on the surface. For some cuboids the shortest surface route has integer length; for others it does not. If \(C(M)\) denotes the number of such cuboids with largest side at most \(M\), the task is to find the least \(M\) for which \(C(M) \gt 10^6\).
A naive search over every triple \((m,b,c)\) is already large, and checking all surface routes for each triple is unnecessary. The implementations use two facts: once the sides are ordered, only one unfolding can be shortest, and the geometry depends on \(b+c\) rather than on \(b\) and \(c\) separately.
The whole method is a counting argument built on a planar unfolding. Instead of tracing a path on a 3D surface, we flatten two faces into a rectangle and turn the shortest route into a straight segment.
With side lengths ordered as \(m \ge b \ge c\), there are three natural ways to unfold two adjacent faces around the start and end corners. They lead to three candidate lengths:
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
Every shortest surface route on a cuboid comes from one of these rectangles, so the problem is to identify which candidate is minimal and when that minimal value is an integer.
Because the sides are sorted, \(d_1\) is always the smallest of the three candidates. It is enough to compare squares:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
So for ordered sides the shortest surface route is always
$$d=\sqrt{m^2+(b+c)^2}.$$
That is the key invariant used by all three implementations.
Now set
$$s=b+c.$$
Since \(1 \le c \le b \le m\), the sum \(s\) satisfies \(2 \le s \le 2m\). The shortest route is integral exactly when
$$m^2+s^2=d^2$$
for some integer \(d\). In other words, \((m,s,d)\) must be a Pythagorean triple. Once \(m\) is fixed, the geometry no longer cares how \(s\) was split into \(b\) and \(c\); it only cares whether \(m^2+s^2\) is a perfect square.
For a fixed admissible pair \((m,s)\), we must count the integer pairs \((b,c)\) with
$$b+c=s, \qquad m \ge b \ge c \ge 1.$$
Writing \(b=s-c\), the inequalities become
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
So \(c\) must lie in the interval
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
Therefore the number of cuboids contributed by this single value of \(s\) is
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
The same count can be written piecewise:
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
This is exactly the interval-length calculation performed in the implementations.
Take \(m=6\) and \(s=8\). Then
$$6^2+8^2=36+64=100=10^2,$$
so any valid split of \(8\) into \(b+c\) gives a cuboid whose shortest surface route has length \(10\). The bounds for \(c\) are
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
Hence \(c\in\{2,3,4\}\), giving the three cuboids
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
All three share the same shortest route length \(10\), because they all correspond to the same pair \((m,s)=(6,8)\).
If \(N(m)\) is the number of new cuboids whose largest side is exactly \(m\), then
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
The cumulative total up to \(M\) is
$$C(M)=\sum_{m=1}^{M} N(m).$$
The answer is the first \(M\) with \(C(M) \gt 10^6\).
The C++, Python, and Java implementations process cuboids by increasing largest side. For each current value they iterate every possible sum of the two smaller sides, from \(2\) up to twice the largest side.
For each candidate sum they form \(m^2+s^2\) and test whether it is a perfect square. The Python implementation uses an integer square root directly. The C++ and Java implementations take the square root numerically, truncate it to an integer, and verify the result by squaring it back. In all three cases the effect is the same: only Pythagorean pairs \((m,s)\) survive.
When a square is found, the implementation computes the lower and upper bounds for \(c\), namely \(\max(1,s-m)\) and \(\min(m,\lfloor s/2 \rfloor)\), and adds the size of that interval. Because the loop already restricts \(s\) to \(2 \le s \le 2m\), the interval is mathematically valid; the code still keeps an explicit guard before adding, which is a harmless safety check.
A running total is maintained across all largest-side values. As soon as that total exceeds the target, the current largest side is returned. The Python implementation uses a fixed outer bound that is comfortably above the true answer, while the C++ and Java implementations keep going until the stopping condition is met. One implementation also includes a small checkpoint: with target \(2000\), the correct least value is \(100\).
For a fixed largest side \(m\), the inner loop visits \(2m-1\) possible sums. Therefore the total number of square tests up to \(M\) is
$$\sum_{m=1}^{M}(2m-1)=M^2,$$
so the running time is \(O(M^2)\). No sorting, recursion, or large auxiliary tables are needed.
The memory usage is \(O(1)\): each implementation stores only a few integers, a square-root result, and the cumulative count.
Betrachte einen Quader mit ganzzahligen Kantenlängen \(m \ge b \ge c \ge 1\). Eine Spinne startet in einer Ecke und will die gegenüberliegende Ecke erreichen, ohne die Oberfläche zu verlassen. Für manche Quader ist die Länge des kürzesten Oberflächenwegs ganzzahlig, für andere nicht. Bezeichnet \(C(M)\) die Anzahl solcher Quader mit größter Kante höchstens \(M\), dann ist die gesuchte Größe das kleinste \(M\) mit \(C(M) \gt 10^6\).
Ein roher Brute-Force-Ansatz würde jedes Tripel \((m,b,c)\) einzeln betrachten und für jedes Tripel mehrere Oberflächenwege prüfen. Die Implementierungen tun etwas viel Schärferes: Nach dem Sortieren der Kanten ist immer dieselbe Entfaltung minimal, und die gesamte Arithmetik hängt nur noch von \(m\) und der Summe \(b+c\) ab.
Die zentrale Idee ist, den Quader so aufzuklappen, dass der kürzeste Oberflächenweg zu einer Geraden in einem Rechteck wird. Damit verschwindet die räumliche Geometrie fast vollständig, und übrig bleibt ein Zahlenthema über Quadratsummen.
Für geordnete Kanten \(m \ge b \ge c\) entstehen aus den drei naheliegenden Entfaltungen die Kandidaten
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
Jeder kürzeste Weg auf der Oberfläche entspricht einer solchen Geraden in einer passenden Entfaltung. Also genügt es, den kleinsten dieser drei Werte zu bestimmen.
Wegen der Ordnung \(m \ge b \ge c\) ist stets \(d_1\) minimal. Wieder genügt der Vergleich der Quadrate:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
Damit ist der kürzeste Oberflächenweg immer
$$d=\sqrt{m^2+(b+c)^2}.$$
Genau diese Beobachtung erlaubt es, die drei Dimensionen auf eine einzige Quadratsummenbedingung zu komprimieren.
Setze
$$s=b+c.$$
Aus \(1 \le c \le b \le m\) folgt sofort \(2 \le s \le 2m\). Der kürzeste Weg ist genau dann ganzzahlig, wenn es ein ganzzahliges \(d\) mit
$$m^2+s^2=d^2$$
gibt. Das ist die Bedingung, dass \((m,s,d)\) ein pythagoreisches Tripel bildet. Für festes \(m\) ist also nur noch wichtig, für welche Summen \(s\) die Zahl \(m^2+s^2\) ein Quadrat ist.
Für ein festes zulässiges Paar \((m,s)\) müssen alle ganzzahligen Paare \((b,c)\) mit
$$b+c=s, \qquad m \ge b \ge c \ge 1$$
gezählt werden. Mit \(b=s-c\) werden die Nebenbedingungen zu
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
Also läuft \(c\) genau über
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
Die Anzahl der zugehörigen Quader lautet daher
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
Äquivalent dazu:
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
Genau diese Intervalllänge berechnen die Implementierungen.
Wähle \(m=6\) und \(s=8\). Dann gilt
$$6^2+8^2=36+64=100=10^2,$$
also liefert jede zulässige Zerlegung von \(8\) in \(b+c\) einen Quader mit ganzzahligem kürzestem Oberflächenweg der Länge \(10\). Für \(c\) erhält man die Schranken
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
Daraus folgen die drei Quader
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
Alle drei werden mit demselben Paar \((m,s)=(6,8)\) gezählt.
Bezeichne mit \(N(m)\) die Anzahl neuer Quader, deren größte Kante genau \(m\) ist. Dann gilt
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
Die kumulierte Gesamtzahl bis \(M\) ist
$$C(M)=\sum_{m=1}^{M} N(m).$$
Gesucht ist das erste \(M\) mit \(C(M) \gt 10^6\).
Die C++-, Python- und Java-Implementierungen durchlaufen die Quader nach wachsender größter Kante. Für jeden aktuellen Wert werden alle möglichen Summen der beiden kleineren Kanten von \(2\) bis \(2m\) geprüft.
Für jede Summe wird \(m^2+s^2\) gebildet und auf Quadratheit getestet. Python verwendet dafür direkt eine ganzzahlige Quadratwurzel. C++ und Java berechnen eine Quadratwurzel, schneiden auf eine ganze Zahl ab und prüfen anschließend durch Rückquadrieren. Ist die Bedingung erfüllt, werden Unter- und Obergrenze für \(c\) bestimmt und die Länge dieses Intervalls zur laufenden Summe addiert.
Sobald die kumulierte Anzahl den Zielwert überschreitet, wird die aktuelle größte Kante ausgegeben. Die Python-Version nutzt eine feste äußere Schranke, die sicher oberhalb der gesuchten Antwort liegt; C++ und Java laufen offen weiter, bis die Schwelle überschritten ist. Eine Implementierung enthält zusätzlich einen kleinen Kontrolltest: Für Zielwert \(2000\) ist das korrekte kleinste Ergebnis \(100\).
Für festes \(m\) hat die innere Schleife \(2m-1\) Iterationen. Bis zu einer Schranke \(M\) ergibt das insgesamt
$$\sum_{m=1}^{M}(2m-1)=M^2,$$
also eine Laufzeit von \(O(M^2)\). Zusätzliche Datenstrukturen werden praktisch nicht benötigt.
Der Speicherverbrauch ist \(O(1)\), weil nur einige Ganzzahlen, ein Quadratwurzelwert und die kumulierte Zählung gehalten werden.
\(m \ge b \ge c \ge 1\) olacak şekilde kenarları tamsayı olan bir dikdörtgenler prizmasını ele alalım. Bir örümcek bir köşeden başlayıp yüzey üzerinde kalarak karşı köşeye gitmek istiyor. Bazı prizmalar için en kısa yüzey yolu tam sayıdır, bazıları için değildir. En büyük kenarı en fazla \(M\) olan ve bu özelliği sağlayan prizma sayısı \(C(M)\) ile gösterilirse, aranan değer \(C(M) \gt 10^6\) eşitsizliğini ilk kez sağlayan en küçük \(M\)'dir.
Ham kuvvet yaklaşımı her \((m,b,c)\) üçlüsünü tek tek dener ve her biri için yüzey üzerindeki aday yolları inceler. Uygulamalar bunu yapmaz. Kenarlar sıralandıktan sonra en kısa yolun hangi açınımdan geldiği sabittir; ardından geometri yalnızca \(m\) ve \(b+c\) toplamına indirgenir.
Temel fikir prizmayı açınıma dönüştürmektir. İki yüz düzleme açıldığında, yüzey üzerindeki en kısa yol bu açınım üzerinde bir doğru parçası haline gelir. Böylece üç boyutlu problem bir sayı kuramı sayımına dönüşür.
Kenarlar \(m \ge b \ge c\) biçiminde sıralandığında üç doğal açınım şu aday uzunlukları verir:
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
Bir yüzey jeodeziği bu dikdörtgenlerden birinde doğrusal hale geldiği için, en kısa yüzey yolunu bulmak bu üç değerden en küçüğünü seçmek demektir.
\(m \ge b \ge c\) sıralaması altında en küçük aday her zaman \(d_1\)'dir. Bunu kareleri karşılaştırarak görürüz:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
Dolayısıyla en kısa yüzey yolu daima
$$d=\sqrt{m^2+(b+c)^2}$$
olur. Çözümün bütün yükü bu tek formülün üzerine kuruludur.
Şimdi
$$s=b+c$$
tanımını yapalım. \(1 \le c \le b \le m\) olduğundan \(2 \le s \le 2m\) aralığında kalırız. En kısa yol ancak ve ancak
$$m^2+s^2=d^2$$
eşitliği bir tam sayı \(d\) için sağlanıyorsa tam sayıdır. Yani \((m,s,d)\) bir Pisagor üçlüsüdür. Sabit bir \(m\) için artık yapılacak iş, yalnızca hangi \(s\) değerlerinde \(m^2+s^2\)'nin tam kare olduğunu test etmektir.
Geçerli bir \((m,s)\) çifti bulduğumuzda, bunun kaç farklı prizmaya karşılık geldiğini saymamız gerekir. Koşullar
$$b+c=s, \qquad m \ge b \ge c \ge 1$$
şeklindedir. \(b=s-c\) yazılırsa
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c$$
elde edilir. Böylece \(c\) için izinli aralık
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor$$
olur. Bu yüzden ilgili prizma sayısı
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1$$
şeklindedir. Aynı ifade parça parça da yazılabilir:
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
Uygulamalar tam olarak bu alt ve üst sınırları hesaplar.
\(m=6\) ve \(s=8\) seçelim. Bu durumda
$$6^2+8^2=36+64=100=10^2,$$
yani \(8\) toplamını veren geçerli her ayrışım, en kısa yüzey yolu \(10\) olan bir prizma üretir. \(c\) için sınırlar
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4$$
olduğundan üç olasılık vardır:
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
Bu üç prizmanın hepsi aynı \((m,s)=(6,8)\) çiftinden gelir ve aynı en kısa yol uzunluğunu paylaşır.
En büyük kenarı tam olarak \(m\) olan yeni prizma sayısını \(N(m)\) ile gösterirsek
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right) $$
olur. Buna göre \(M\)'ye kadar toplam sayı
$$C(M)=\sum_{m=1}^{M}N(m)$$
ve cevap da \(C(M) \gt 10^6\) koşulunu sağlayan ilk \(M\)'dir.
C++, Python ve Java uygulamaları, prizmaları artan en büyük kenara göre işler. Her adımda iki küçük kenarın toplamı olabilecek tüm değerler \(2\) ile \(2m\) arasında taranır.
Her toplam için \(m^2+s^2\) hesaplanır ve bunun tam kare olup olmadığı kontrol edilir. Python tam sayılı karekök kullanır. C++ ve Java ise karekök alıp tam sayıya indirger, sonra geri karesini alarak doğrulama yapar. Test geçerse \(c\) için alt ve üst sınırlar bulunur; aralığın uzunluğu toplam sayaca eklenir.
Toplam sayı hedefi geçtiği anda mevcut en büyük kenar sonuç olarak döndürülür. Python sürümü, doğru cevabın altında kalmayacak sabit bir dış sınır kullanır; C++ ve Java sürümleri ise eşik aşılana kadar devam eder. Çözümlerden biri ayrıca küçük bir doğrulama içerir: hedef \(2000\) seçildiğinde en küçük sonuç \(100\) olmalıdır.
Sabit bir \(m\) için iç döngü \(2m-1\) toplam dener. Bu yüzden \(M\)'ye kadar yapılan tam kare testlerinin toplam sayısı
$$\sum_{m=1}^{M}(2m-1)=M^2$$
olur; dolayısıyla çalışma süresi \(O(M^2)\)'dir. Büyük ek tablolar veya karmaşık veri yapıları kullanılmaz.
Bellek kullanımı \(O(1)\)'dir; yalnızca birkaç tamsayı, karekök sonucu ve birikimli sayaç tutulur.
Considérese un ortoedro con aristas enteras \(m \ge b \ge c \ge 1\). Una araña parte de un vértice y quiere llegar al vértice opuesto sin abandonar la superficie. Para algunos ortoedros la longitud de la ruta superficial más corta es un entero; para otros no. Si \(C(M)\) denota el número de ortoedros con arista mayor a lo sumo \(M\) y ruta mínima entera, el objetivo es hallar el menor \(M\) tal que \(C(M) \gt 10^6\).
Una búsqueda directa sobre todos los triples \((m,b,c)\) sería innecesariamente costosa. Las implementaciones explotan dos simplificaciones: con las aristas ordenadas siempre gana el mismo desarrollo plano, y la condición geométrica depende de \(m\) y de la suma \(b+c\), no de \(b\) y \(c\) por separado.
La idea central es desplegar dos caras del ortoedro en el plano. En ese despliegue, la geodésica superficial buscada se convierte en un segmento recto. El problema tridimensional queda reducido a una condición pitagórica y a un conteo combinatorio.
Con las aristas ordenadas como \(m \ge b \ge c\), los tres desarrollos naturales producen las longitudes candidatas
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
Cualquier ruta superficial mínima aparece como una recta en uno de estos rectángulos. Por tanto, basta con identificar cuál de los tres candidatos es siempre el menor.
Bajo la hipótesis \(m \ge b \ge c\), el mínimo siempre es \(d_1\). Basta comparar cuadrados:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
Así, la longitud mínima de superficie es siempre
$$d=\sqrt{m^2+(b+c)^2}.$$
Ese es exactamente el objeto matemático que usan los tres programas.
Definamos
$$s=b+c.$$
Como \(1 \le c \le b \le m\), se tiene \(2 \le s \le 2m\). La ruta mínima es entera si y solo si existe un entero \(d\) tal que
$$m^2+s^2=d^2.$$
Por tanto \((m,s,d)\) debe ser una terna pitagórica. Una vez fijado \(m\), la única pregunta geométrica es: ¿para qué valores de \(s\) la suma \(m^2+s^2\) es un cuadrado perfecto?
Si un par \((m,s)\) es válido, todavía hay que contar cuántos pares enteros \((b,c)\) cumplen
$$b+c=s, \qquad m \ge b \ge c \ge 1.$$
Escribiendo \(b=s-c\), las restricciones pasan a ser
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
Luego \(c\) recorre exactamente el intervalo
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
El número de ortoedros aportado por ese \(s\) es entonces
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
Equivalente en forma por casos:
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
Eso coincide exactamente con la cuenta de límites inferior y superior que hace la implementación.
Tómese \(m=6\) y \(s=8\). Entonces
$$6^2+8^2=36+64=100=10^2,$$
de modo que toda descomposición válida de \(8\) como \(b+c\) produce un ortoedro cuya ruta mínima mide \(10\). Los límites para \(c\) son
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
Esto da exactamente tres ortoedros:
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
Los tres provienen del mismo par \((m,s)=(6,8)\) y por eso comparten la misma longitud mínima.
Si \(N(m)\) es el número de nuevos ortoedros cuya arista mayor vale exactamente \(m\), entonces
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
La cantidad acumulada hasta \(M\) es
$$C(M)=\sum_{m=1}^{M}N(m),$$
y la respuesta es el primer \(M\) para el que \(C(M) \gt 10^6\).
Las implementaciones en C++, Python y Java procesan los ortoedros por orden creciente de la arista mayor. Para cada valor actual recorren todas las sumas posibles de las dos aristas menores, desde \(2\) hasta \(2m\).
Para cada suma candidata calculan \(m^2+s^2\) y comprueban si es un cuadrado perfecto. Python usa una raíz cuadrada entera exacta. C++ y Java calculan la raíz cuadrada, la convierten a entero y verifican el resultado al volver a elevar al cuadrado. En los tres casos, solo sobreviven los pares \((m,s)\) que producen una terna pitagórica.
Cuando la prueba es positiva, el programa obtiene los límites inferior y superior para \(c\) y suma el tamaño de ese intervalo. Se mantiene un total acumulado a través de todos los valores de la arista mayor. En cuanto ese total supera el objetivo, se devuelve el valor actual. La versión de Python usa un límite externo fijo que queda por encima de la respuesta real; las versiones de C++ y Java continúan hasta que la condición de parada se cumple. Una de las implementaciones también incluye una comprobación auxiliar: para objetivo \(2000\), el menor valor correcto es \(100\).
Para un valor fijo de \(m\), el bucle interno examina \(2m-1\) sumas. Por lo tanto, hasta un límite \(M\) se realizan
$$\sum_{m=1}^{M}(2m-1)=M^2$$
pruebas de cuadrado perfecto, lo que da un tiempo total \(O(M^2)\). No hay estructuras auxiliares grandes.
El uso de memoria es \(O(1)\), porque solo se mantienen unos pocos enteros, una raíz cuadrada y el contador acumulado.
设一个长方体的边长为整数 \(m \ge b \ge c \ge 1\)。蜘蛛从一个顶点出发，只能沿表面爬到对角的顶点。对某些长方体来说，最短表面路径的长度是整数；对另一些则不是。记 \(C(M)\) 为最大边长不超过 \(M\) 且最短表面路径为整数的长方体个数，题目要求找到满足 \(C(M) \gt 10^6\) 的最小 \(M\)。
如果直接枚举每个 \((m,b,c)\) 再分别检查各种走法，计算量会很大，而且很多工作是重复的。三份实现都利用了两个关键事实：当边长已经按大小排序后，最短路径总来自同一种展开方式；并且几何条件只依赖于 \(m\) 与 \(b+c\)，而不依赖于 \(b\) 和 \(c\) 的具体拆分方式。
核心思路是把长方体的两个相邻面展开到平面上。这样一来，原本在三维表面上的最短路径就变成了平面矩形中的一条直线，问题随之化为一个关于平方和与计数区间的问题。
在 \(m \ge b \ge c\) 的排序下，三种自然展开会给出三条候选路径：
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
长方体表面上的最短路线一定对应其中某个展开图中的直线段，因此问题首先变成：这三个候选值里哪一个真正最短？
由于边长已经满足 \(m \ge b \ge c\)，最小值总是 \(d_1\)。只需比较平方：
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
因此最短表面路径恒为
$$d=\sqrt{m^2+(b+c)^2}.$$
这一步非常重要，因为它说明根本不需要在代码中比较三个展开式，只要检查这一条公式即可。
记
$$s=b+c.$$
由 \(1 \le c \le b \le m\) 可知 \(2 \le s \le 2m\)。最短路径为整数，当且仅当存在整数 \(d\) 满足
$$m^2+s^2=d^2.$$
也就是说，\((m,s,d)\) 必须构成一组勾股三元组。对固定的最大边 \(m\) 而言，几何部分已经完全转化为一个判定：哪些 \(s\) 会使 \(m^2+s^2\) 成为完全平方数。
即使某个 \((m,s)\) 通过了完全平方判定，也还要计算它对应多少个不同的长方体。我们需要统计所有满足
$$b+c=s, \qquad m \ge b \ge c \ge 1$$
的整数对 \((b,c)\)。把 \(b\) 写成 \(s-c\) 之后，不等式变为
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
于是 \(c\) 的取值范围恰好是
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
因此，对应的长方体个数为
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
把它写成分段形式更直观：
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
这正是实现中通过上下界求区间长度的那一步。
取 \(m=6\)、\(s=8\)。此时
$$6^2+8^2=36+64=100=10^2,$$
说明只要 \(b+c=8\) 且满足排序条件，对应长方体的最短表面路径长度就都是 \(10\)。由上面的界可得
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
所以 \(c\) 可以取 \(2,3,4\)，对应三组边长：
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
它们虽然形状不同，但都来自同一个 \((m,s)=(6,8)\)，因此在计数时会被一起加入。
记 \(N(m)\) 为最大边恰好等于 \(m\) 时新增的长方体数量，则
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
于是到 \(M\) 为止的累计总数为
$$C(M)=\sum_{m=1}^{M}N(m).$$
题目要找的就是第一个满足 \(C(M) \gt 10^6\) 的 \(M\)。
C++、Python 和 Java 实现都按最大边从小到大枚举。对每一个当前最大边，它们都会遍历两条较短边之和的全部可能值，即从 \(2\) 到 \(2m\)。
对每个候选和，程序都会计算 \(m^2+s^2\) 并检查它是否为完全平方。Python 版本使用整数平方根；C++ 和 Java 版本先取平方根、截断为整数，再通过回平方验证。三者的数学效果完全相同：只保留能够形成勾股三元组的 \((m,s)\)。
一旦判定通过，实现就计算 \(c\) 的下界与上界，并把这个整数区间的长度加入累计总数。虽然循环范围已经保证 \(2 \le s \le 2m\)，因此区间在数学上是成立的，代码仍然保留了一个显式的非空检查，这只是一个稳妥的保护。
程序持续维护一个总计数，一旦超过目标，就返回当前的最大边。Python 版本使用一个固定的外层上界，而 C++ 与 Java 版本则一直递增直到触发停止条件。还有一个实现包含了小型校验：如果目标改成 \(2000\)，那么最小结果应当是 \(100\)。
对固定的 \(m\)，内层循环检查 \(2m-1\) 个候选和。因此枚举到 \(M\) 时，总的完全平方检测次数是
$$\sum_{m=1}^{M}(2m-1)=M^2,$$
所以总时间复杂度为 \(O(M^2)\)。整个过程中不需要排序、递归或大型辅助表。
空间复杂度为 \(O(1)\)，因为只保存少量整数、一个平方根结果以及累计计数。
Рассматривается прямоугольный параллелепипед с целыми рёбрами \(m \ge b \ge c \ge 1\). Паук находится в одном углу и должен добраться до противоположного угла, не сходя с поверхности. Для одних параллелепипедов длина кратчайшего поверхностного пути является целым числом, для других нет. Если \(C(M)\) обозначает число таких тел с наибольшим ребром не больше \(M\), то нужно найти наименьшее \(M\), для которого \(C(M) \gt 10^6\).
Полный перебор всех троек \((m,b,c)\) с отдельной проверкой всех раскладок поверхности был бы избыточен. Реальные реализации используют более точную структуру задачи: после упорядочивания рёбер минимальным оказывается один и тот же тип развёртки, а вся арифметика зависит только от \(m\) и суммы \(b+c\).
Ключевой шаг состоит в том, чтобы развернуть две соседние грани в плоскость. Тогда кратчайший путь по поверхности становится обычным отрезком в прямоугольнике, а задача сводится к проверке квадратов и к подсчёту числа допустимых разбиений суммы.
При порядке \(m \ge b \ge c\) три естественные развёртки дают три кандидатные длины:
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
Любой кратчайший поверхностный маршрут на прямоугольном параллелепипеде получается как прямая линия в одном из этих прямоугольников. Значит, сначала нужно понять, какой из трёх кандидатов всегда минимален.
Из-за упорядочения \(m \ge b \ge c\) минимальным всегда является \(d_1\). Сравним квадраты:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
Следовательно, кратчайший путь всегда имеет длину
$$d=\sqrt{m^2+(b+c)^2}.$$
Именно поэтому все три реализации сразу работают только с этой формулой, не сравнивая три варианта каждый раз.
Обозначим
$$s=b+c.$$
Из неравенств \(1 \le c \le b \le m\) следует диапазон \(2 \le s \le 2m\). Кратчайший путь является целым тогда и только тогда, когда существует целое \(d\), удовлетворяющее
$$m^2+s^2=d^2.$$
То есть тройка \((m,s,d)\) должна быть пифагоровой. После фиксации \(m\) геометрия уже полностью сводится к вопросу о том, для каких сумм \(s\) число \(m^2+s^2\) является полным квадратом.
Если пара \((m,s)\) прошла квадратный тест, нужно ещё посчитать количество целочисленных пар \((b,c)\), для которых
$$b+c=s, \qquad m \ge b \ge c \ge 1.$$
Подставим \(b=s-c\). Тогда условия превращаются в
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
Значит, \(c\) пробегает интервал
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
Отсюда число подходящих параллелепипедов равно
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
В эквивалентной кусочной форме:
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
Именно эту длину целочисленного интервала и добавляет программа.
Возьмём \(m=6\) и \(s=8\). Тогда
$$6^2+8^2=36+64=100=10^2,$$
значит, любое допустимое разложение \(8=b+c\) даст параллелепипед с кратчайшим поверхностным путём длины \(10\). Для \(c\) получаем границы
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
Следовательно, возникают три тела:
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
Все они считаются вместе, потому что соответствуют одной и той же паре \((m,s)=(6,8)\).
Пусть \(N(m)\) обозначает число новых тел, у которых наибольшее ребро равно ровно \(m\). Тогда
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
Суммарное количество до границы \(M\) равно
$$C(M)=\sum_{m=1}^{M}N(m).$$
Ответом является первое \(M\), для которого \(C(M) \gt 10^6\).
Реализации на C++, Python и Java идут по возрастанию наибольшего ребра. Для каждого текущего значения они перебирают все возможные суммы двух меньших рёбер, от \(2\) до \(2m\).
Для каждой суммы вычисляется \(m^2+s^2\) и проверяется, является ли это число полным квадратом. В Python используется целочисленный квадратный корень. В C++ и Java берётся квадратный корень, отбрасывается дробная часть и выполняется обратная проверка возведением в квадрат. Если тест пройден, вычисляются нижняя и верхняя границы для \(c\), и длина этого интервала прибавляется к общему счётчику.
Поддерживается накопительный итог по всем значениям наибольшего ребра. Как только он превышает целевое значение, текущее ребро и есть ответ. Версия на Python использует фиксированную внешнюю границу, заведомо превосходящую настоящий ответ; версии на C++ и Java продолжают работу до выполнения условия остановки. В одной из реализаций есть и небольшой контрольный тест: при цели \(2000\) правильный минимальный результат равен \(100\).
Для фиксированного \(m\) внутренний цикл выполняется \(2m-1\) раз. Следовательно, число проверок до предела \(M\) равно
$$\sum_{m=1}^{M}(2m-1)=M^2,$$
поэтому время работы составляет \(O(M^2)\). Никаких больших вспомогательных структур не требуется.
Память используется в объёме \(O(1)\): несколько целых чисел, значение квадратного корня и накопительный счётчик.
نأخذ متوازي مستطيلات أبعاده الصحيحة \(m \ge b \ge c \ge 1\). يبدأ العنكبوت من أحد الرؤوس ويريد الوصول إلى الرأس المقابل مع البقاء على السطح. بعض هذه الأجسام يكون طول أقصر مسار سطحي فيها عددًا صحيحًا، وبعضها لا يكون كذلك. إذا رمزنا بعدد الأجسام التي لا يزيد أكبر ضلع فيها على \(M\) ولها أقصر مسار صحيح بالرمز \(C(M)\)، فالمطلوب هو أصغر \(M\) يحقق \(C(M) \gt 10^6\).
الفحص المباشر لكل ثلاثية \((m,b,c)\) مع تجربة كل المسارات السطحية الممكنة سيكون مكلفًا أكثر مما يلزم. الفكرة التي تعتمدها التطبيقات أبسط وأقوى: بعد ترتيب الأضلاع نعرف أي نشر للشكل يعطي المسار الأقصر دائمًا، ثم يصبح الشرط كله متعلقًا بـ \(m\) وبالمجموع \(b+c\) فقط.
جوهر الحل هو فرد وجهين متجاورين من الجسم على مستوى واحد. عندئذ يتحول أقصر مسار على السطح إلى قطعة مستقيمة داخل مستطيل، وتتحول المسألة من هندسة فراغية إلى شرط فيثاغورسي وعدٍّ لعدد التجزئات الممكنة.
بعد ترتيب الأضلاع على الصورة \(m \ge b \ge c\)، تظهر ثلاثة أطوال مرشحة من النشرات الطبيعية المختلفة:
$$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$$
أي مسار سطحي أقصر لا بد أن يقابل خطًا مستقيمًا في أحد هذه المستطيلات، لذلك يجب أولًا تحديد أي طول من هذه الأطوال الثلاثة هو الأصغر فعلًا.
بسبب الترتيب \(m \ge b \ge c\)، يكون \(d_1\) دائمًا هو الأصغر. يكفي مقارنة المربعات:
$$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$$
$$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$$
إذن أقصر مسار سطحي هو دائمًا
$$d=\sqrt{m^2+(b+c)^2}.$$
هذه هي الحقيقة الأساسية التي تبني عليها التطبيقات كلها حسابها.
لنضع
$$s=b+c.$$
ومن العلاقة \(1 \le c \le b \le m\) نحصل على المجال \(2 \le s \le 2m\). يكون طول أقصر مسار عددًا صحيحًا إذا وفقط إذا وُجد عدد صحيح \(d\) يحقق
$$m^2+s^2=d^2.$$
أي إن \((m,s,d)\) يجب أن تكون ثلاثية فيثاغورس. بعد تثبيت \(m\)، لم نعد نهتم بشكل الجسم بالتفصيل، بل فقط بأي قيم \(s\) تجعل \(m^2+s^2\) مربعًا كاملًا.
إذا كانت \((m,s)\) صالحة، فما زال علينا عدّ الأزواج الصحيحة \((b,c)\) التي تحقق
$$b+c=s, \qquad m \ge b \ge c \ge 1.$$
بكتابة \(b=s-c\) تتحول الشروط إلى
$$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$$
ومن ثم فإن \(c\) يتحرك داخل المجال
$$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$$
إذن عدد الأجسام التي يضيفها هذا المجموع هو
$$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$$
ويمكن كتابته أيضًا على صورتين حسب موقع \(s\):
$$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $$
وهذا يطابق تمامًا ما تحسبه التطبيقات من حد أدنى وحد أعلى ثم طول الفترة بينهما.
لنأخذ \(m=6\) و \(s=8\). عندئذ
$$6^2+8^2=36+64=100=10^2,$$
وبالتالي فإن كل تفكيك صالح للعدد \(8\) على صورة \(b+c\) يعطي جسمًا يكون طول أقصر مسار على سطحه مساويًا لـ \(10\). حدود \(c\) تصبح
$$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$$
إذن نحصل على الأجسام الثلاثة
$$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$$
هذه الأجسام الثلاثة مختلفة، لكنها كلها تنتج من الزوج نفسه \((m,s)=(6,8)\)، ولذلك تُضاف دفعة واحدة.
إذا رمزنا بعدد الأجسام الجديدة التي يكون أكبر ضلع فيها مساويًا تمامًا لـ \(m\) بالرمز \(N(m)\)، فإن
$$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $$
وعندئذ يكون العدد التراكمي حتى \(M\) هو
$$C(M)=\sum_{m=1}^{M}N(m).$$
والجواب المطلوب هو أول \(M\) يحقق \(C(M) \gt 10^6\).
تسير تطبيقات C++ وPython وJava بترتيب تصاعدي لأكبر ضلع. ولكل قيمة حالية، تجرّب جميع المجاميع الممكنة للضلعين الأصغر، من \(2\) حتى \(2m\).
لكل مجموع مرشح، يُحسب \(m^2+s^2\) ثم يُفحص ما إذا كان مربعًا كاملًا. إصدار Python يستخدم جذرًا تربيعيًا صحيحًا مباشرًا. أما إصدارا C++ وJava فيحسبان الجذر التربيعي عدديًا، ثم يحولانه إلى عدد صحيح، ثم يعيدان التربيع للتحقق. النتيجة الرياضية واحدة في جميع الأحوال: لا يُحتفظ إلا بالأزواج \((m,s)\) التي تصنع ثلاثية فيثاغورس.
عندما ينجح الاختبار، يحسب التنفيذ الحدين الأدنى والأعلى لـ \(c\) ثم يضيف طول هذا المجال إلى العداد التراكمي. صحيح أن المجال الرياضي يكون صالحًا أصلًا داخل الحلقة \(2 \le s \le 2m\)، لكن الكود يحتفظ أيضًا بفحص صريح لعدم فراغ المجال، وهو فحص احترازي لا يغير الفكرة.
يبقى هناك مجموع جارٍ عبر جميع قيم أكبر ضلع. ما إن يتجاوز هذا المجموع الهدف حتى تُعاد القيمة الحالية لأكبر ضلع. إصدار Python يستعمل حدًا خارجيًا ثابتًا أعلى من الجواب الحقيقي، بينما يواصل إصدارا C++ وJava الزيادة حتى تتحقق عتبة التوقف. وتوجد أيضًا معايرة صغيرة في أحد الحلول: إذا كان الهدف \(2000\)، فالنتيجة الدنيا الصحيحة هي \(100\).
عند تثبيت \(m\)، تحتوي الحلقة الداخلية على \(2m-1\) قيمة ممكنة للمجموع. لذلك يكون عدد اختبارات المربع الكامل حتى حد \(M\) مساويًا لـ
$$\sum_{m=1}^{M}(2m-1)=M^2,$$
ومن ثم يكون الزمن الكلي \(O(M^2)\). لا توجد بنى بيانات كبيرة أو عمليات فرز أو استدعاء تراجعي.
أما الذاكرة فهي \(O(1)\)، لأن التنفيذ لا يحتفظ إلا بعدة أعداد صحيحة وقيمة جذر تربيعي وعداد تراكمي.