Problem 247 builds an infinite family of axis-aligned squares inside the region below the rectangular hyperbola \(y=1/x\), starting from the corner \((1,0)\). From any exposed lower-left corner \((x,y)\), the next square is defined to be the unique largest square anchored at that corner whose upper-right corner still lies on the curve.
Each square receives a label \((\text{left},\text{below})\). Moving to the right child increases \(\text{left}\) by 1, and moving to the upper child increases \(\text{below}\) by 1. All squares are then ranked globally by decreasing side length, not by tree depth. The actual target in this problem is the last square labeled \((3,3)\), so the task is to determine where the 20th such square appears in that global size order.
The geometry gives a closed formula for the next square, and the recursive construction turns naturally into a best-first search on exposed corners. The crucial point is that the code never tries to list squares in depth-first or breadth-first order; it always extracts the currently largest available square.
Fix a corner \((x,y)\) with \(x > 0\) and \(0 \le y < 1/x\). Let \(t=t(x,y)\) be the side length of the largest square whose lower-left corner is \((x,y)\) and whose sides remain parallel to the axes. The square occupies \([x,x+t]\times[y,y+t]\), so maximality occurs exactly when its upper-right corner touches the hyperbola:
$$y+t=\frac{1}{x+t}.$$
Multiplying through gives a quadratic equation:
$$t^2+(x+y)t+(xy-1)=0.$$
The positive root is
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
This is the quantity computed in all three implementations. Because every generated corner stays strictly below the curve, the expression under the square root is positive and the chosen root is the unique feasible side length.
Once the square of side \(t\) has been placed at \((x,y)\), two new exposed lower-left corners matter for the continuation:
$$\text{right child}: (x+t,y),\qquad \text{upper child}: (x,y+t).$$
Those two children correspond exactly to the two ways a later square can first touch the placed square: along its right side or along its top side. If a square has label \((L,B)\), then its children have labels
$$ (L+1,B)\qquad\text{and}\qquad (L,B+1). $$
So the whole construction is a binary tree of corners. The geometric data of a node are the corner \((x,y)\) and the induced side \(t(x,y)\); the combinatorial data are the two label counters \((L,B)\).
The ranking required by the problem is global: at every step we need the largest square among all squares that could ever appear later, not just among the children of the most recently processed node. The key monotonicity fact is that moving right or upward can only shrink the next square. If \(x_1 \ge x_0\) and \(y_1 \ge y_0\), with at least one inequality strict, then the feasible region under \(y=1/x\) above \((x_1,y_1)\) is smaller than the one above \((x_0,y_0)\), hence
$$t(x_1,y_1) < t(x_0,y_0).$$
Therefore every descendant of a node is strictly smaller than that node. At any moment, every unseen square is a descendant of one of the corners already sitting on the frontier, so the largest unseen square must already be present on that frontier. A max-heap over side lengths is therefore enough to reproduce the exact global order demanded by the problem.
The label recurrence is purely combinatorial. To reach \((L,B)\), one must take \(L\) right moves and \(B\) up moves in some order. If \(N(L,B)\) is the number of nodes with that label, then the tree structure gives Pascal's recurrence
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
with boundary values \(N(L,0)=N(0,B)=1\). Hence
$$N(L,B)=\binom{L+B}{L}.$$
For the actual target \((3,3)\), this means
$$N(3,3)=\binom{6}{3}=20.$$
So the correct stopping rule is not “stop at the first \((3,3)\) square”. The algorithm must continue until the 20th such square has been popped from the heap, because that pop index is the required answer.
The root corner is \((1,0)\), so the first square has side
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
Its right child is anchored at \((1+t(1,0),0)\approx(1.61803,0)\), with side
$$t(1.61803,0)\approx 0.4772599965.$$
Its upper child is anchored at \((1,t(1,0))\approx(1,0.61803)\), with side
$$t(1,0.61803)\approx 0.2090569265.$$
Now look at label \((1,1)\). There are two paths to it, \(RU\) and \(UR\), so there are two distinct squares. Their sides are approximately
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
The labels match, but the sizes do not. The \(UR\) square appears earlier in the global ranking because it is larger. This small example is exactly why the code counts occurrences of a target label instead of stopping at the first match.
The C++, Python, and Java implementations all follow the same best-first search, differing only in language syntax and numeric types.
Each heap entry stores four pieces of information: the current label \((\text{left},\text{below})\), the geometric corner \((x,y)\), and the side length obtained from the closed formula above. The priority key is simply the side length, ordered so that the largest pending square is removed first.
The search starts with the root corner \((1,0)\). Whenever the implementation pops the current maximum from the heap, that pop number is exactly the square's global index. If the popped label is \((3,3)\), the counter of seen target squares is incremented. Then the implementation computes the right and upper child corners, evaluates their side lengths with the same hyperbola formula, and pushes both children into the heap.
Because there are exactly \(\binom{6}{3}=20\) squares labeled \((3,3)\), the loop stops when the 20th one is popped. The stored pop counter at that moment is the desired index. No post-processing is needed: the heap order is already the ranking order defined by the problem statement.
Let \(A(L,B)\) denote the index of the last square with label \((L,B)\) in the global size order. To solve the target \((L,B)\), the implementation must perform exactly \(A(L,B)\) heap pops. Each pop is paired with two pushes, and each heap operation costs \(O(\log M)\) when the heap currently contains \(M\) elements.
Therefore the running time is \(O(A(L,B)\log A(L,B))\). After \(M\) pops the heap contains \(M+1\) nodes, so the memory usage is \(O(A(L,B))\). For the concrete Project Euler target \((3,3)\), this is easily practical.
Problem 247 konstruiert unendlich viele achsenparallele Quadrate im Gebiet unter der rechteckigen Hyperbel \(y=1/x\), beginnend mit der Ecke \((1,0)\). Von jeder freiliegenden linken unteren Ecke \((x,y)\) aus wird immer das eindeutig größte Quadrat eingesetzt, das dort verankert ist und dessen rechte obere Ecke noch auf der Kurve liegt.
Jedes Quadrat erhält ein Label \((\text{left},\text{below})\). Ein Schritt zum rechten Kind erhöht \(\text{left}\) um 1, ein Schritt zum oberen Kind erhöht \(\text{below}\) um 1. Anschließend werden alle Quadrate global nach absteigender Seitenlänge geordnet, nicht nach Baumtiefe. Im eigentlichen Problem wird der Index des letzten Quadrats mit Label \((3,3)\) gesucht; da es davon 20 Stück gibt, geht es also um die Position des 20. Auftretens in dieser Größenordnung.
Die Geometrie liefert eine geschlossene Formel für das jeweils nächste Quadrat, und die rekursive Konstruktion wird dadurch zu einer Best-First-Suche über freiliegende Ecken. Entscheidend ist, dass der Code die Quadrate nicht in Tiefen- oder Breitenreihenfolge auflistet, sondern immer das aktuell größte verfügbare Quadrat auswählt.
Fixiere eine Ecke \((x,y)\) mit \(x > 0\) und \(0 \le y < 1/x\). Sei \(t=t(x,y)\) die Seitenlänge des größten Quadrats mit linker unterer Ecke \((x,y)\). Das Quadrat belegt \([x,x+t]\times[y,y+t]\); im Optimum berührt seine rechte obere Ecke die Hyperbel, also gilt
$$y+t=\frac{1}{x+t}.$$
Nach dem Ausmultiplizieren entsteht die quadratische Gleichung
$$t^2+(x+y)t+(xy-1)=0.$$
Die positive Lösung ist
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
Genau diese Größe berechnen alle drei Implementierungen. Weil jede erzeugte Ecke strikt unterhalb der Kurve bleibt, ist der Ausdruck unter der Wurzel positiv, und die gewählte Lösung ist die eindeutig zulässige Seitenlänge.
Nachdem an \((x,y)\) ein Quadrat der Seitenlänge \(t\) gesetzt wurde, sind für die Fortsetzung genau zwei neue linke untere Ecken relevant:
$$\text{rechtes Kind}: (x+t,y),\qquad \text{oberes Kind}: (x,y+t).$$
Diese beiden Kinder entsprechen genau den zwei Möglichkeiten, wie ein späteres Quadrat das gerade gesetzte Quadrat zuerst berühren kann: an seiner rechten Seite oder an seiner oberen Seite. Hat ein Quadrat das Label \((L,B)\), dann tragen seine Kinder die Labels
$$ (L+1,B)\qquad\text{und}\qquad (L,B+1). $$
Damit ist die gesamte Konstruktion ein binärer Baum von Ecken. Die geometrischen Zustandsdaten eines Knotens sind die Ecke \((x,y)\) und die daraus folgende Seitenlänge \(t(x,y)\); die kombinatorischen Zustandsdaten sind die beiden Labelzähler \((L,B)\).
Die im Problem verlangte Ordnung ist global: In jedem Schritt braucht man das größte Quadrat unter allen Quadraten, die irgendwann noch auftreten können, nicht nur unter den Kindern des zuletzt bearbeiteten Knotens. Die entscheidende Monotonie lautet: Wer nach rechts oder nach oben rückt, verkleinert das nächste mögliche Quadrat. Gilt \(x_1 \ge x_0\) und \(y_1 \ge y_0\), wobei mindestens eine Ungleichung strikt ist, dann ist das unter \(y=1/x\) oberhalb von \((x_1,y_1)\) verbleibende Gebiet kleiner als oberhalb von \((x_0,y_0)\), also
$$t(x_1,y_1) < t(x_0,y_0).$$
Jeder Nachfahre eines Knotens ist deshalb strikt kleiner als der Knoten selbst. Zu jedem Zeitpunkt ist jedes noch unsichtbare Quadrat ein Nachfahre einer Ecke auf der aktuellen Front. Folglich muss das größte noch unsichtbare Quadrat bereits auf dieser Front liegen. Eine Max-Heap-Struktur über den Seitenlängen reproduziert daher exakt die globale Reihenfolge aus der Aufgabenstellung.
Die Labelrekurrenz ist rein kombinatorisch. Um \((L,B)\) zu erreichen, braucht man \(L\) Schritte nach rechts und \(B\) Schritte nach oben in irgendeiner Reihenfolge. Bezeichnet \(N(L,B)\) die Zahl der Knoten mit diesem Label, dann liefert die Baumstruktur die Pascal-Rekurrenz
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
mit Randwerten \(N(L,0)=N(0,B)=1\). Also gilt
$$N(L,B)=\binom{L+B}{L}.$$
Für das tatsächliche Ziel \((3,3)\) folgt damit
$$N(3,3)=\binom{6}{3}=20.$$
Die korrekte Abbruchbedingung lautet also nicht „beim ersten \((3,3)\)-Quadrat stoppen“. Der Algorithmus muss bis zum 20. entnommenen \((3,3)\)-Knoten weiterlaufen, denn dessen Entnahmeindex ist die gesuchte Antwort.
Die Wurzelecke ist \((1,0)\); das erste Quadrat hat also die Seitenlänge
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
Sein rechtes Kind ist bei \((1+t(1,0),0)\approx(1.61803,0)\) verankert und hat Seitenlänge
$$t(1.61803,0)\approx 0.4772599965.$$
Sein oberes Kind ist bei \((1,t(1,0))\approx(1,0.61803)\) verankert und hat Seitenlänge
$$t(1,0.61803)\approx 0.2090569265.$$
Nun zum Label \((1,1)\). Es gibt genau zwei Wege dorthin, nämlich \(RU\) und \(UR\), also auch zwei verschiedene Quadrate. Ihre Seitenlängen sind näherungsweise
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
Die Labels stimmen überein, die Größen aber nicht. Das \(UR\)-Quadrat erscheint in der globalen Ordnung früher, weil es größer ist. Dieses kleine Beispiel zeigt genau, warum der Code die Anzahl der Treffer eines Labels mitzählt, statt beim ersten Treffer abzubrechen.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Best-First-Suche; nur Syntax und Zahlentypen unterscheiden sich.
Jeder Heap-Eintrag speichert vier Informationen: das aktuelle Label \((\text{left},\text{below})\), die geometrische Ecke \((x,y)\) und die aus der geschlossenen Formel berechnete Seitenlänge. Als Priorität dient ausschließlich die Seitenlänge, so dass immer das größte noch ausstehende Quadrat zuerst entnommen wird.
Die Suche beginnt bei der Wurzelecke \((1,0)\). Immer wenn die Implementierung das aktuelle Maximum aus dem Heap entnimmt, ist genau diese Entnahmenummer der globale Index des Quadrats. Trägt das entnommene Quadrat das Label \((3,3)\), wird der Zielzähler erhöht. Danach werden die rechte und die obere Kindsecke berechnet, ihre Seitenlängen mit derselben Hyperbelformel ausgewertet und beide Kinder wieder in den Heap gelegt.
Weil es genau \(\binom{6}{3}=20\) Quadrate mit Label \((3,3)\) gibt, stoppt die Schleife beim 20. solchen Pop. Der zu diesem Zeitpunkt gespeicherte Pop-Zähler ist bereits der gesuchte Index. Eine nachträgliche Sortierung ist nicht nötig: Die Heap-Reihenfolge ist genau die durch die Aufgabe definierte Größenreihenfolge.
Sei \(A(L,B)\) der Index des letzten Quadrats mit Label \((L,B)\) in der globalen Größenordnung. Um das Ziel \((L,B)\) zu lösen, muss die Implementierung genau \(A(L,B)\) Heap-Pops ausführen. Zu jedem Pop kommen zwei Pushes hinzu, und jede Heap-Operation kostet \(O(\log M)\), wenn der Heap aktuell \(M\) Elemente enthält.
Damit ergibt sich eine Laufzeit von \(O(A(L,B)\log A(L,B))\). Nach \(M\) Pops enthält der Heap genau \(M+1\) Knoten, also liegt der Speicherverbrauch bei \(O(A(L,B))\). Für das konkrete Project-Euler-Ziel \((3,3)\) ist das problemlos praktikabel.
Problem 247, \(y=1/x\) dik hiperbolünün altındaki bölgede sonsuz sayıda eksenlere paralel kare üretir ve başlangıç köşesi \((1,0)\)'dır. Her açık sol-alt köşe \((x,y)\) için, o köşeye oturan ve sağ üst köşesi eğriye değen tek en büyük kare yerleştirilir.
Her kare \((\text{left},\text{below})\) etiketi taşır. Sağ çocuğa gitmek \(\text{left}\) sayısını 1 artırır, üst çocuğa gitmek \(\text{below}\) sayısını 1 artırır. Daha sonra kareler ağaç derinliğine göre değil, kenar uzunluklarına göre küresel olarak sıralanır. Sorunun gerçek hedefi \((3,3)\) etiketli son karedir; bu etikete sahip tam 20 kare bulunduğu için, aranan şey bu 20. karenin küresel sıralamadaki indeksidir.
Geometri, sıradaki karenin kapalı formülünü doğrudan veriyor; özyinelemeli yapı da bunu açık köşeler üzerinde en büyükten küçüğe giden bir aramaya dönüştürüyor. Esas fikir, kareleri derinlik öncelikli ya da genişlik öncelikli üretmek değil, o anda mümkün olan en büyük kareyi çekmektir.
\(x > 0\) ve \(0 \le y < 1/x\) koşullarını sağlayan bir \((x,y)\) köşesi alalım. \((x,y)\) noktasına oturan en büyük karenin kenarına \(t=t(x,y)\) diyelim. Kare \([x,x+t]\times[y,y+t]\) bölgesini kaplar; maksimum durumda sağ üst köşe hiperbola değmek zorundadır:
$$y+t=\frac{1}{x+t}.$$
Bu eşitlik açılınca ikinci dereceden denklem gelir:
$$t^2+(x+y)t+(xy-1)=0.$$
Pozitif kök şudur:
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
Üç uygulamanın da hesapladığı nicelik budur. Üretilen her köşe eğrinin altında kaldığı için kökün içi pozitiftir ve seçilen kök tek geçerli kenar uzunluğudur.
\((x,y)\) köşesine kenarı \(t\) olan kare yerleştirildikten sonra devam için önemli olan yeni sol-alt köşeler tam olarak şunlardır:
$$\text{sağ çocuk}: (x+t,y),\qquad \text{üst çocuk}: (x,y+t).$$
Bu iki çocuk, ileride gelecek bir karenin mevcut kareye ilk temasını ya sağ kenarından ya da üst kenarından yapmasına karşılık gelir. Bir karenin etiketi \((L,B)\) ise çocukların etiketleri
$$ (L+1,B)\qquad\text{ve}\qquad (L,B+1) $$
olur. Böylece tüm yapı bir köşe ikili ağacına dönüşür. Bir düğümün geometrik durumu \((x,y)\) köşesi ve bundan türeyen \(t(x,y)\) kenarıdır; kombinatorik durumu ise \((L,B)\) etiket çiftidir.
Sorunun istediği sıralama küreseldir: Her adımda yalnızca son işlenen düğümün çocukları arasında değil, ileride ortaya çıkabilecek bütün kareler arasında en büyüğünü seçmek gerekir. Buradaki temel monotonluk şudur: sağa veya yukarı gitmek, sıradaki karenin boyunu küçültür. Eğer \(x_1 \ge x_0\) ve \(y_1 \ge y_0\) olup en az biri sıkı ise, \(y=1/x\) altında \((x_1,y_1)\) üzerinden erişilebilen bölge, \((x_0,y_0)\) üzerinden erişilebilen bölgeden daha küçüktür; dolayısıyla
$$t(x_1,y_1) < t(x_0,y_0).$$
Yani her torun kare, atasından kesin olarak daha küçüktür. Her anda henüz görülmemiş her kare, mevcut sınırdaki köşelerden birinin torunudur. Bu yüzden henüz görülmemiş en büyük kare zaten sınır üzerinde bulunmak zorundadır. Kenar uzunluğunu anahtar yapan bir max-heap, problemin istediği küresel sıralamayı tam olarak yeniden üretir.
Etiketlerin sayımı tamamen kombinatoriktir. \((L,B)\) etiketine ulaşmak için toplam \(L\) kez sağa, \(B\) kez yukarı gidilir; sıra değişebilir. \((L,B)\) etiketli düğüm sayısı \(N(L,B)\) olsun. Ağaç yapısı Pascal bağıntısını verir:
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
ve sınır değerler \(N(L,0)=N(0,B)=1\)'dir. Sonuç olarak
$$N(L,B)=\binom{L+B}{L}.$$
Gerçek hedef için
$$N(3,3)=\binom{6}{3}=20$$
elde edilir. Bu yüzden doğru durma koşulu “ilk \((3,3)\) karesinde dur” değildir. Algoritma, heap'ten çıkan 20. \((3,3)\) düğümüne kadar devam etmelidir; aranan indeks tam o pop numarasıdır.
Kök köşe \((1,0)\)'dır; ilk karenin kenarı
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
Sağ çocuk \((1+t(1,0),0)\approx(1.61803,0)\) köşesine oturur ve kenarı
$$t(1.61803,0)\approx 0.4772599965$$
olur. Üst çocuk ise \((1,t(1,0))\approx(1,0.61803)\) köşesindedir ve kenarı
$$t(1,0.61803)\approx 0.2090569265$$
çıkar. Şimdi \((1,1)\) etiketine bakalım. Buraya iki yol vardır: \(RU\) ve \(UR\). Dolayısıyla iki farklı kare oluşur ve bunların kenarları yaklaşık olarak
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862$$
şeklindedir. Etiketler aynı olsa da boyutlar aynı değildir. \(UR\) karesi daha büyük olduğu için küresel sıralamada daha erken gelir. Bu küçük örnek, kodun neden ilk eşleşmede durmak yerine hedef etiketin tüm görünümlerini saydığını açıkça gösterir.
C++, Python ve Java uygulamalarının üçü de aynı en-büyükten-küçüğe aramayı uygular; sadece sözdizimi ve kullandıkları kayan nokta türleri farklıdır.
Heap'teki her kayıt dört bilgi taşır: mevcut \((\text{left},\text{below})\) etiketi, geometrik \((x,y)\) köşesi ve yukarıdaki kapalı formülden hesaplanan kenar uzunluğu. Öncelik anahtarı yalnızca kenar uzunluğudur; böylece bekleyen kareler arasındaki en büyük olan önce çekilir.
Arama \((1,0)\) köşesiyle başlar. Uygulama heap'ten mevcut maksimumu her çektiğinde, o çekme sayısı karenin küresel indeksidir. Çıkan etiket \((3,3)\) ise görülen hedef kare sayısı bir artırılır. Ardından sağ ve üst çocuk köşeleri oluşturulur, aynı hiperbol formülüyle yeni kenarlar hesaplanır ve iki çocuk da heap'e geri eklenir.
\((3,3)\) etiketli kare sayısı tam olarak \(\binom{6}{3}=20\) olduğu için döngü 20. böyle kare pop edildiğinde sona erer. O anda tutulan pop sayacı doğrudan istenen indekstir. Ek bir sıralama ya da düzeltme adımı gerekmez; heap sırası zaten problemde tanımlanan sıralamadır.
\(A(L,B)\), küresel boy sıralamasında \((L,B)\) etiketli son karenin indeksi olsun. Hedef \((L,B)\) için çözüm üretmek adına uygulama tam olarak \(A(L,B)\) adet heap pop işlemi yapar. Her pop'a iki push eşlik eder ve heap üzerinde her işlem, o anda heap'te \(M\) eleman varsa \(O(\log M)\) maliyetlidir.
Dolayısıyla toplam süre \(O(A(L,B)\log A(L,B))\), bellek kullanımı ise \(O(A(L,B))\) olur. Gerçek Project Euler hedefi olan \((3,3)\) için bu maliyet son derece pratiktir.
El problema 247 construye una familia infinita de cuadrados alineados con los ejes dentro de la región situada bajo la hipérbola rectangular \(y=1/x\), comenzando en la esquina \((1,0)\). Desde cualquier esquina inferior izquierda expuesta \((x,y)\), se inserta el cuadrado más grande posible anclado en esa esquina y cuya esquina superior derecha todavía toca la curva.
Cada cuadrado recibe una etiqueta \((\text{left},\text{below})\). Moverse al hijo derecho incrementa \(\text{left}\) en 1, y moverse al hijo superior incrementa \(\text{below}\) en 1. Después, todos los cuadrados se ordenan globalmente por longitud de lado decreciente, no por profundidad en el árbol. En el problema real se pide el índice del último cuadrado etiquetado \((3,3)\); como existen exactamente 20 apariciones de esa etiqueta, lo que hay que localizar es la posición de la vigésima aparición dentro del orden global por tamaño.
La geometría da una fórmula cerrada para el siguiente cuadrado, y la construcción recursiva se convierte de manera natural en una búsqueda best-first sobre esquinas expuestas. La idea esencial es que el código no enumera los cuadrados en orden de profundidad, sino en el orden real exigido por el problema: siempre extrae el cuadrado disponible más grande.
Fijemos una esquina \((x,y)\) con \(x > 0\) y \(0 \le y < 1/x\). Sea \(t=t(x,y)\) la longitud del lado del mayor cuadrado cuya esquina inferior izquierda es \((x,y)\). Ese cuadrado ocupa \([x,x+t]\times[y,y+t]\), así que en el caso máximo su esquina superior derecha debe tocar la hipérbola:
$$y+t=\frac{1}{x+t}.$$
Al multiplicar, aparece una ecuación cuadrática:
$$t^2+(x+y)t+(xy-1)=0.$$
La raíz positiva es
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
Esa es exactamente la cantidad calculada por las tres implementaciones. Como toda esquina generada permanece estrictamente por debajo de la curva, el radicando es positivo y la raíz elegida es la única longitud de lado geométricamente válida.
Una vez colocado en \((x,y)\) el cuadrado de lado \(t\), las dos nuevas esquinas inferiores izquierdas relevantes para continuar son
$$\text{hijo derecho}: (x+t,y),\qquad \text{hijo superior}: (x,y+t).$$
Estos dos hijos representan exactamente las dos formas en que un cuadrado futuro puede tocar por primera vez el cuadrado ya colocado: por el lado derecho o por el lado superior. Si un cuadrado tiene etiqueta \((L,B)\), entonces sus hijos llevan las etiquetas
$$ (L+1,B)\qquad\text{y}\qquad (L,B+1). $$
Por tanto, toda la construcción se organiza como un árbol binario de esquinas. Los datos geométricos de un nodo son la esquina \((x,y)\) y el lado inducido \(t(x,y)\); los datos combinatorios son los dos contadores de la etiqueta \((L,B)\).
El orden requerido es global: en cada paso hace falta elegir el cuadrado más grande entre todos los que podrán aparecer más adelante, no solo entre los hijos del nodo recién procesado. El hecho de monotonía crucial es que avanzar a la derecha o hacia arriba solo puede reducir el siguiente cuadrado. Si \(x_1 \ge x_0\) y \(y_1 \ge y_0\), con al menos una desigualdad estricta, entonces la región factible bajo \(y=1/x\) por encima de \((x_1,y_1)\) es menor que la correspondiente a \((x_0,y_0)\), y por eso
$$t(x_1,y_1) < t(x_0,y_0).$$
Así, todo descendiente es estrictamente más pequeño que su ancestro. En cualquier instante, cada cuadrado todavía no visto es descendiente de alguna esquina que ya está en la frontera actual. Por consiguiente, el mayor cuadrado no visto tiene que estar ya en esa frontera. Un max-heap sobre las longitudes de lado basta entonces para reproducir exactamente el ranking global pedido por el enunciado.
La recurrencia de las etiquetas es puramente combinatoria. Para llegar a \((L,B)\), hay que realizar \(L\) movimientos a la derecha y \(B\) movimientos hacia arriba, en algún orden. Si \(N(L,B)\) denota el número de nodos con esa etiqueta, la estructura del árbol da la recurrencia de Pascal
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
con condiciones de borde \(N(L,0)=N(0,B)=1\). De ahí resulta
$$N(L,B)=\binom{L+B}{L}.$$
Para el objetivo real,
$$N(3,3)=\binom{6}{3}=20.$$
Por eso la condición de parada correcta no es “detenerse en el primer cuadrado \((3,3)\)”. El algoritmo debe continuar hasta extraer el vigésimo cuadrado con esa etiqueta, porque el número de extracción en ese momento es precisamente la respuesta buscada.
La esquina raíz es \((1,0)\), de modo que el primer cuadrado tiene lado
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
Su hijo derecho está anclado en \((1+t(1,0),0)\approx(1.61803,0)\) y tiene lado
$$t(1.61803,0)\approx 0.4772599965.$$
Su hijo superior está anclado en \((1,t(1,0))\approx(1,0.61803)\) y tiene lado
$$t(1,0.61803)\approx 0.2090569265.$$
Consideremos ahora la etiqueta \((1,1)\). Hay dos caminos para llegar a ella, \(RU\) y \(UR\), así que aparecen dos cuadrados distintos. Sus lados son aproximadamente
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
La etiqueta es la misma, pero el tamaño no. El cuadrado \(UR\) aparece antes en el orden global porque es mayor. Este ejemplo pequeño muestra exactamente por qué el código cuenta cuántas apariciones de la etiqueta objetivo ha visto, en lugar de detenerse en la primera.
Las implementaciones en C++, Python y Java siguen la misma búsqueda best-first; solo cambian la sintaxis y el tipo numérico concreto.
Cada entrada de la cola almacena cuatro datos: la etiqueta actual \((\text{left},\text{below})\), la esquina geométrica \((x,y)\) y la longitud del lado calculada con la fórmula cerrada. La clave de prioridad es únicamente esa longitud, ordenada para que el cuadrado pendiente más grande salga primero.
La búsqueda comienza en la esquina raíz \((1,0)\). Cada vez que la implementación extrae el máximo actual de la cola, ese número de extracción es exactamente el índice global del cuadrado. Si la etiqueta extraída es \((3,3)\), se incrementa el contador de apariciones objetivo. Luego se calculan las esquinas del hijo derecho y del hijo superior, se evalúan sus lados con la misma fórmula de la hipérbola y ambos se insertan de nuevo en la cola.
Como existen exactamente \(\binom{6}{3}=20\) cuadrados con etiqueta \((3,3)\), el bucle termina cuando se extrae el vigésimo. El contador de extracciones almacenado en ese instante ya es el índice buscado. No hace falta ninguna ordenación adicional: el orden del heap coincide con el ranking definido por el problema.
Sea \(A(L,B)\) el índice del último cuadrado con etiqueta \((L,B)\) en el orden global por tamaños. Para resolver el objetivo \((L,B)\), la implementación realiza exactamente \(A(L,B)\) extracciones del heap. Cada extracción va acompañada de dos inserciones, y cada operación sobre el heap cuesta \(O(\log M)\) cuando el heap contiene \(M\) elementos.
En consecuencia, el tiempo total es \(O(A(L,B)\log A(L,B))\). Tras \(M\) extracciones, el heap contiene \(M+1\) nodos, de modo que el uso de memoria es \(O(A(L,B))\). Para el objetivo concreto \((3,3)\) de Project Euler, este coste es perfectamente manejable.
第 247 题研究的是在矩形双曲线 \(y=1/x\) 下方递归放置无穷多个与坐标轴平行的正方形，起点是角点 \((1,0)\)。对于任意一个已经暴露出来的左下角 \((x,y)\)，都放入一个以它为左下角、且右上角刚好还能碰到曲线的最大正方形。
每个正方形都带有一个 \((\text{left},\text{below})\) 标签。走向右子节点时，\(\text{left}\) 加 1；走向上子节点时，\(\text{below}\) 加 1。题目要求的排序不是递归树中的先后顺序，而是所有正方形按边长从大到小的全局顺序。这个问题真正要求的是标签为 \((3,3)\) 的最后一个正方形的序号；由于这种标签一共会出现 20 次，所以本质上要找的是第 20 次出现时在全局边长排序中的位置。
这道题的核心有两层。第一层是几何：从一个角点出发，最大正方形的边长可以直接写成闭式公式。第二层是搜索策略：既然题目要的是全局按边长排序的次序，算法就必须始终优先处理当前所有候选中最大的那个正方形。
设某个可行角点为 \((x,y)\)，其中 \(x > 0\) 且 \(0 \le y < 1/x\)。记从这个角点出发能放下的最大正方形边长为 \(t=t(x,y)\)。这个正方形占据区域 \([x,x+t]\times[y,y+t]\)。如果它还可以再变大，那么右上角就还没有碰到双曲线；因此在最大情形下必有
$$y+t=\frac{1}{x+t}.$$
把它化成多项式方程可得
$$t^2+(x+y)t+(xy-1)=0.$$
其中符合几何意义的正根是
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
这就是三种实现真正计算的对象。由于所有生成出来的角点都严格位于曲线下方，所以根号内部始终为正，而上式给出的正根就是唯一可行的边长。
在角点 \((x,y)\) 处放入边长为 \(t\) 的正方形之后，后续递归只需要关心两个新的左下角：
$$\text{右子角点}: (x+t,y),\qquad \text{上子角点}: (x,y+t).$$
这两个角点分别对应于“未来的正方形第一次贴着当前正方形的右边出现”以及“未来的正方形第一次贴着当前正方形的上边出现”这两种情况。如果某个节点的标签是 \((L,B)\)，那么它的两个子节点标签分别变成
$$ (L+1,B)\qquad\text{和}\qquad (L,B+1). $$
因此，程序真正遍历的对象不是一个普通的区域分割，而是一棵由角点构成的二叉树。每个节点同时带有几何信息 \((x,y,t)\) 和组合信息 \((L,B)\)。
题目要求的不是“先访问父节点，再访问子节点”这样的树遍历顺序，而是“在所有将来可能出现的正方形中，当前最大的那个先编号”。这一步成立依赖于一个单调性事实：只要角点往右或往上移动，下一个可放入的最大正方形就一定变小。也就是说，如果 \(x_1 \ge x_0\) 且 \(y_1 \ge y_0\)，并且至少有一个不等号是严格的，那么由 \((x_1,y_1)\) 出发能容纳的正方形一定比由 \((x_0,y_0)\) 出发的小，因此
$$t(x_1,y_1) < t(x_0,y_0).$$
这意味着任何节点的后代都严格小于该节点本身。于是，在任意时刻，所有还没有出现的正方形都一定是当前边界上某个候选节点的后代，而这些后代绝不可能比它们的祖先更大。所以“尚未出现的最大正方形”必然已经在当前边界中。用一个按边长排序的最大堆维护这条边界，就能精确重现题目定义的全局排序。
标签计数完全来自组合结构。要到达标签 \((L,B)\)，必须总共走 \(L\) 次右分支和 \(B\) 次上分支，只是顺序可以不同。若记 \(N(L,B)\) 为标签 \((L,B)\) 出现的次数，那么二叉树结构直接给出 Pascal 递推：
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
边界条件是 \(N(L,0)=N(0,B)=1\)。因此
$$N(L,B)=\binom{L+B}{L}.$$
对于本题目标，
$$N(3,3)=\binom{6}{3}=20.$$
这就说明程序绝不能在第一次弹出 \((3,3)\) 时就停止。它必须持续运行，直到第 20 个 \((3,3)\) 节点被弹出为止；那一刻的弹出编号才是题目所求。
根角点是 \((1,0)\)，因此第一个正方形的边长为
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
它的右子节点角点是 \((1+t(1,0),0)\approx(1.61803,0)\)，对应边长
$$t(1.61803,0)\approx 0.4772599965.$$
它的上子节点角点是 \((1,t(1,0))\approx(1,0.61803)\)，对应边长
$$t(1,0.61803)\approx 0.2090569265.$$
现在看标签 \((1,1)\)。到达它有两条路径：\(RU\) 和 \(UR\)，因此会得到两个不同的正方形。它们的边长分别约为
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
可以看到，标签相同并不意味着大小相同。由于 \(UR\) 产生的那个正方形更大，所以它会在全局排序中更早出现。这个小例子正好解释了为什么实现必须“统计目标标签已经出现了多少次”，而不是“一旦第一次命中就退出”。
C++、Python 和 Java 三个实现执行的是同一套 best-first 搜索逻辑，只是语法和浮点类型不同。
堆中的每个条目都保存当前标签 \((\text{left},\text{below})\)、当前角点 \((x,y)\)，以及利用上面的闭式公式算出的边长。优先级键只有一个，就是边长本身，并按照“边长越大优先级越高”的规则组织。
搜索从根角点 \((1,0)\) 开始。每次从堆中弹出当前最大的候选时，这个弹出的次序编号就是该正方形在全局中的排名。如果它的标签是 \((3,3)\)，就把目标计数器加 1。然后根据右子角点和上子角点的坐标公式生成两个孩子，再用同样的双曲线公式计算它们的边长，并重新压回堆中。
因为标签 \((3,3)\) 一共恰好出现 \(\binom{6}{3}=20\) 次，所以循环在第 20 次弹出该标签时终止。此时保存的弹出编号就是最终答案，不需要额外排序，也不需要回头修正；堆的弹出顺序已经等同于题目定义的序号顺序。
记 \(A(L,B)\) 为标签 \((L,B)\) 的最后一次出现，在全局边长排序中的编号。为了求解目标 \((L,B)\)，实现恰好会执行 \(A(L,B)\) 次堆弹出操作。每次弹出伴随两次插入，而堆操作在当前堆大小为 \(M\) 时需要 \(O(\log M)\) 时间。
因此总时间复杂度是 \(O(A(L,B)\log A(L,B))\)。在进行了 \(M\) 次弹出之后，堆中恰好会保留 \(M+1\) 个节点，所以空间复杂度是 \(O(A(L,B))\)。对本题真正需要的 \((3,3)\) 来说，这个复杂度完全可接受。
В задаче 247 строится бесконечное семейство квадратов со сторонами, параллельными осям, внутри области под прямоугольной гиперболой \(y=1/x\), начиная с угла \((1,0)\). Для каждого открытого левого нижнего угла \((x,y)\) берется единственный наибольший квадрат, который можно поставить с этой вершиной так, чтобы его правая верхняя вершина еще касалась кривой.
Каждый квадрат получает метку \((\text{left},\text{below})\). Переход к правому потомку увеличивает \(\text{left}\) на 1, переход к верхнему потомку увеличивает \(\text{below}\) на 1. Затем все квадраты упорядочиваются глобально по убыванию длины стороны, а не по глубине рекурсии. В самой задаче требуется индекс последнего квадрата с меткой \((3,3)\); поскольку такая метка встречается ровно 20 раз, нужно найти позицию 20-го появления в глобальном порядке по размеру.
Геометрия дает явную формулу для следующего квадрата, а рекурсивная конструкция естественным образом превращается в best-first поиск по открытым углам. Главная идея состоит в том, что квадратов нельзя перечислять просто по дереву; нужно всегда извлекать крупнейший из всех доступных в данный момент кандидатов.
Зафиксируем угол \((x,y)\), где \(x > 0\) и \(0 \le y < 1/x\). Обозначим через \(t=t(x,y)\) длину стороны наибольшего квадрата с левой нижней вершиной в \((x,y)\). Такой квадрат занимает область \([x,x+t]\times[y,y+t]\), поэтому в максимальном случае его правая верхняя вершина должна лежать на гиперболе:
$$y+t=\frac{1}{x+t}.$$
После преобразования получаем квадратное уравнение
$$t^2+(x+y)t+(xy-1)=0.$$
Его положительный корень равен
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
Именно эту величину вычисляют все три реализации. Так как каждый сгенерированный угол остается строго ниже кривой, подкоренное выражение положительно, и выбранный положительный корень является единственной допустимой длиной стороны.
После того как в углу \((x,y)\) размещен квадрат со стороной \(t\), для продолжения важны ровно два новых левых нижних угла:
$$\text{правый потомок}: (x+t,y),\qquad \text{верхний потомок}: (x,y+t).$$
Эти два потомка соответствуют двум способам, которыми более поздний квадрат может впервые примкнуть к уже поставленному квадрату: к его правой стороне или к его верхней стороне. Если текущая метка равна \((L,B)\), то у потомков метки становятся
$$ (L+1,B)\qquad\text{и}\qquad (L,B+1). $$
Тем самым вся конструкция задает бинарное дерево углов. Геометрическое состояние узла состоит из угла \((x,y)\) и порождаемой им стороны \(t(x,y)\); комбинаторное состояние состоит из двух счетчиков метки \((L,B)\).
Порядок в задаче глобальный: на каждом шаге нужен самый большой квадрат среди всех квадратов, которые вообще могут появиться позднее, а не только среди детей последнего обработанного узла. Ключевой факт монотонности таков: смещение вправо или вверх уменьшает следующий возможный квадрат. Если \(x_1 \ge x_0\) и \(y_1 \ge y_0\), причем хотя бы одно неравенство строгое, то допустимая область под \(y=1/x\) над точкой \((x_1,y_1)\) меньше, чем над \((x_0,y_0)\), а значит
$$t(x_1,y_1) < t(x_0,y_0).$$
Следовательно, любой потомок строго меньше своего предка. В любой момент каждый еще не увиденный квадрат является потомком какого-то узла на текущей границе. Значит, наибольший из еще не увиденных квадратов уже обязан лежать на этой границе. Поэтому max-heap по длинам сторон в точности воспроизводит тот глобальный порядок, который задан в условии.
Рекурсия по меткам чисто комбинаторна. Чтобы дойти до \((L,B)\), нужно сделать \(L\) шагов вправо и \(B\) шагов вверх в некотором порядке. Пусть \(N(L,B)\) обозначает число узлов с такой меткой. Тогда дерево дает рекурсию Паскаля
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
с граничными условиями \(N(L,0)=N(0,B)=1\). Отсюда следует
$$N(L,B)=\binom{L+B}{L}.$$
Для реальной цели получаем
$$N(3,3)=\binom{6}{3}=20.$$
Поэтому правильное условие остановки звучит не как «остановиться на первом квадрате \((3,3)\)». Алгоритм обязан продолжать работу до тех пор, пока из кучи не будет извлечен 20-й квадрат с такой меткой, потому что именно номер этого извлечения и есть ответ.
Корневой угол равен \((1,0)\), поэтому первый квадрат имеет сторону
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
Его правый потомок привязан к углу \((1+t(1,0),0)\approx(1.61803,0)\) и имеет сторону
$$t(1.61803,0)\approx 0.4772599965.$$
Его верхний потомок привязан к углу \((1,t(1,0))\approx(1,0.61803)\) и имеет сторону
$$t(1,0.61803)\approx 0.2090569265.$$
Теперь рассмотрим метку \((1,1)\). До нее ведут два пути, \(RU\) и \(UR\), значит существуют два разных квадрата. Их стороны приблизительно равны
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
Метка одна и та же, а размеры различаются. Квадрат \(UR\) появляется раньше в глобальном порядке, потому что он больше. Именно этот пример показывает, почему реализация должна считать количество появлений нужной метки, а не останавливаться при первом совпадении.
Реализации на C++, Python и Java выполняют один и тот же best-first поиск; различаются только синтаксис и конкретные типы чисел с плавающей точкой.
Каждый элемент кучи хранит текущую метку \((\text{left},\text{below})\), текущий геометрический угол \((x,y)\) и длину стороны, вычисленную по приведенной выше формуле. Единственным приоритетным ключом служит сама длина стороны, поэтому первым извлекается самый большой ожидающий квадрат.
Поиск стартует из корневого угла \((1,0)\). Каждый раз, когда реализация извлекает текущий максимум из кучи, номер этого извлечения совпадает с глобальным индексом квадрата. Если извлеченная метка равна \((3,3)\), счетчик целевых появлений увеличивается на 1. Затем вычисляются правый и верхний дочерние углы, для них снова считается длина стороны по той же формуле гиперболы, и оба потомка помещаются обратно в кучу.
Так как квадратов с меткой \((3,3)\) ровно \(\binom{6}{3}=20\), цикл заканчивается при извлечении двадцатого такого квадрата. Сохраненный к этому моменту номер извлечения уже является искомым индексом. Дополнительная сортировка не нужна: порядок извлечения из кучи и есть порядок, определенный в условии задачи.
Обозначим через \(A(L,B)\) индекс последнего квадрата с меткой \((L,B)\) в глобальном порядке по размеру. Чтобы решить задачу для цели \((L,B)\), реализация выполняет ровно \(A(L,B)\) извлечений из кучи. Каждому извлечению соответствуют две вставки, а каждая операция с кучей стоит \(O(\log M)\), если в куче сейчас \(M\) элементов.
Отсюда общее время работы равно \(O(A(L,B)\log A(L,B))\). После \(M\) извлечений в куче остается \(M+1\) узлов, поэтому потребление памяти равно \(O(A(L,B))\). Для фактической цели \((3,3)\) из задачи Project Euler это полностью практично.
تعالج المسألة 247 بناء عائلة لا نهائية من المربعات المتوازية مع المحورين داخل المنطقة الواقعة تحت القطع الزائد المستطيل \(y=1/x\)، مع نقطة البداية عند الزاوية \((1,0)\). لكل زاوية سفلية يسرى ظاهرة \((x,y)\)، نضع أكبر مربع ممكن ركنه السفلي الأيسر هو تلك الزاوية وتبقى زاويته العليا اليمنى على المنحنى.
كل مربع يحمل الوسم \((\text{left},\text{below})\). الانتقال إلى الابن الأيمن يزيد \(\text{left}\) بمقدار 1، والانتقال إلى الابن العلوي يزيد \(\text{below}\) بمقدار 1. بعد ذلك لا تُرتَّب المربعات بحسب عمق الشجرة، بل بحسب أطوال الأضلاع ترتيبًا عالميًا تنازليًا. في المسألة الفعلية المطلوب هو فهرس آخر مربع يحمل الوسم \((3,3)\). وبما أن هذا الوسم يظهر بالضبط 20 مرة، فالمطلوب عمليًا هو موضع الظهور العشرين داخل هذا الترتيب العالمي حسب الحجم.
الهندسة تعطي صيغة مغلقة لطول ضلع المربع التالي، والبناء التكراري يتحول طبيعيًا إلى بحث من نوع best-first على الزوايا الظاهرة. الفكرة الأساسية هي أن الشيفرة لا تستعرض المربعات بترتيب الشجرة، بل تنتزع دائمًا أكبر مربع متاح حاليًا لأنه هو التالي في الترتيب المطلوب.
ثبّت زاوية \((x,y)\) تحقق \(x > 0\) و\(0 \le y < 1/x\). ولتكن \(t=t(x,y)\) طول ضلع أكبر مربع يمكن وضعه بحيث تكون زاويته السفلى اليسرى عند \((x,y)\). هذا المربع يشغل المستطيل \([x,x+t]\times[y,y+t]\)، ولذلك ففي الحالة العظمى يجب أن تلامس زاويته العليا اليمنى القطع الزائد:
$$y+t=\frac{1}{x+t}.$$
وبعد الضرب والترتيب نحصل على المعادلة التربيعية
$$t^2+(x+y)t+(xy-1)=0.$$
وجذرها الموجب هو
$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$
هذه هي الكمية التي تحسبها تطبيقات C++ وPython وJava فعلًا. وبما أن كل زاوية مولدة تبقى أسفل المنحنى بدقة، فإن ما داخل الجذر يبقى موجبًا، ويكون هذا الجذر الموجب هو طول الضلع الوحيد المقبول هندسيًا.
بعد وضع مربع طوله \(t\) عند الزاوية \((x,y)\)، توجد زاويتان سفليتان يسريتان جديدتان فقط تهمان المتابعة:
الابن الأيمن: \((x+t,y)\)
الابن العلوي: \((x,y+t)\)
هاتان الزاويتان تمثلان الطريقتين الوحيدتين اللتين يمكن بهما لمربع لاحق أن يلامس المربع الحالي أول مرة: إما عبر ضلعه الأيمن أو عبر ضلعه العلوي. وإذا كان وسم مربع ما هو \((L,B)\)، فإن وسمَي ابنيه يصبحان \((L+1,B)\) و\((L,B+1)\).
إذن فالبناء كله عبارة عن شجرة ثنائية من الزوايا. الحالة الهندسية للعقدة هي \((x,y)\) مع طول الضلع الناتج \(t(x,y)\)، أما الحالة التوافقية فهي زوج العدّادين \((L,B)\).
الترتيب المطلوب في نص المسألة ترتيب عالمي: في كل خطوة يجب اختيار أكبر مربع بين جميع المربعات التي قد تظهر لاحقًا، لا مجرد أكبر ابن للعقدة التي عولجت أخيرًا. والحقيقة الأحادية الأساسية هنا هي أن الانتقال يمينًا أو أعلى لا يمكن إلا أن يصغّر المربع التالي. فإذا كان \(x_1 \ge x_0\) و\(y_1 \ge y_0\) مع كون إحدى المتباينتين على الأقل صارمة، فإن المنطقة الممكنة تحت \(y=1/x\) فوق \((x_1,y_1)\) أصغر من المنطقة الممكنة فوق \((x_0,y_0)\)، ومن ثم
$$t(x_1,y_1) < t(x_0,y_0).$$
وبذلك يكون كل سليل أصغر من سلفه قطعًا. وفي أي لحظة يكون كل مربع لم يُر بعد سليلًا لإحدى الزوايا الموجودة حاليًا على الحدود الأمامية. لذا فإن أكبر مربع غير مرئي بعد لا بد أن يكون موجودًا أصلًا على تلك الحدود. لهذا يكفي استعمال max-heap مرتبة بحسب طول الضلع كي نحصل على الترتيب العالمي نفسه الذي تفرضه المسألة.
عدّ الوسوم مسألة توافقية خالصة. للوصول إلى \((L,B)\) لا بد من تنفيذ \(L\) انتقالات إلى اليمين و\(B\) انتقالات إلى الأعلى بترتيب ما. إذا رمزنا بعدد العقد ذات الوسم \((L,B)\) بالرمز \(N(L,B)\)، فإن بنية الشجرة تعطي علاقة باسكال
$$N(L,B)=N(L-1,B)+N(L,B-1),$$
مع الشروط الحدية \(N(L,0)=N(0,B)=1\). ومن ثم
$$N(L,B)=\binom{L+B}{L}.$$
وبالنسبة إلى الهدف الحقيقي نحصل على
$$N(3,3)=\binom{6}{3}=20.$$
لهذا فإن شرط التوقف الصحيح ليس “قف عند أول مربع وسمه \((3,3)\)”. بل يجب أن تستمر الخوارزمية حتى سحب المربع العشرين ذي هذا الوسم من الكومة، لأن رقم هذا السحب هو الجواب المطلوب.
زاوية الجذر هي \((1,0)\)، ولذلك يكون ضلع أول مربع
$$t(1,0)=\frac{\sqrt{5}-1}{2}\approx 0.6180339887.$$
الابن الأيمن مثبت عند \((1+t(1,0),0)\approx(1.61803,0)\)، وطول ضلعه
$$t(1.61803,0)\approx 0.4772599965.$$
أما الابن العلوي فمثبت عند \((1,t(1,0))\approx(1,0.61803)\)، وطول ضلعه
$$t(1,0.61803)\approx 0.2090569265.$$
لننظر الآن إلى الوسم \((1,1)\). توجد طريقان للوصول إليه، هما \(RU\) و\(UR\)، ولذلك ينتج مربعان مختلفان. طولا ضلعيهما تقريبًا هما
$$t_{RU}\approx 0.1035877034,\qquad t_{UR}\approx 0.1292042862.$$
الوسم واحد، لكن الحجم ليس واحدًا. يظهر مربع \(UR\) أبكر في الترتيب العالمي لأنه أكبر. وهذا المثال الصغير يوضح بدقة لماذا تعدّ الشيفرة عدد مرات ظهور الوسم الهدف بدل أن تتوقف عند أول تطابق.
تتبع تطبيقات C++ وPython وJava المنهج نفسه تمامًا في البحث من الأكبر إلى الأصغر، مع اختلافات لغوية فقط في الصياغة ونوع الأعداد العشرية المستخدمة.
كل عنصر في الكومة يخزن الوسم الحالي \((\text{left},\text{below})\)، والزاوية الهندسية \((x,y)\)، وطول الضلع المحسوب من الصيغة المغلقة السابقة. مفتاح الأولوية الوحيد هو طول الضلع، بحيث يكون المربع الأكبر بين المعلّقين هو أول ما يُسحب.
يبدأ البحث من زاوية الجذر \((1,0)\). وفي كل مرة تسحب فيها الشيفرة أكبر عنصر حالي من الكومة، يكون رقم هذا السحب هو الفهرس العالمي لذلك المربع. وإذا كان وسم المربع المسحوب هو \((3,3)\)، فإن عدّاد مرات الظهور الهدف يزداد بمقدار واحد. بعد ذلك تُحسب زاويتا الابن الأيمن والابن العلوي، وتُحسب أطوال أضلاعهما بالصيغة نفسها، ثم يُعاد إدخالهما في الكومة.
لأن عدد المربعات ذات الوسم \((3,3)\) يساوي تمامًا \(\binom{6}{3}=20\)، فإن الحلقة تنتهي عند سحب المربع العشرين من هذا النوع. وعند تلك اللحظة يكون عدّاد السحب المخزن هو الفهرس المطلوب مباشرة. لا حاجة إلى فرز إضافي ولا إلى تصحيح لاحق، لأن ترتيب السحب من الكومة هو نفسه ترتيب المسألة.
لنرمز بـ \(A(L,B)\) إلى فهرس آخر مربع يحمل الوسم \((L,B)\) داخل الترتيب العالمي بحسب الحجم. من أجل حل الهدف \((L,B)\)، تنفذ الشيفرة بالضبط \(A(L,B)\) عمليات سحب من الكومة. وكل سحب يتبعه إدخالان، وكل عملية على الكومة تكلف \(O(\log M)\) عندما يكون عدد عناصرها الحالي \(M\).
إذًا يكون زمن التنفيذ الكلي \(O(A(L,B)\log A(L,B))\)، أما الذاكرة فهي \(O(A(L,B))\). وبعد \(M\) عمليات سحب يبقى في الكومة \(M+1\) عنصرًا. بالنسبة إلى الهدف الفعلي \((3,3)\) في Project Euler، فهذا التعقيد عملي تمامًا.