The Heighway Dragon in this problem is generated from the symbolic rule set \(D_0=Fa\), together with the substitutions \(a\to aRbFR\) and \(b\to LFaLb\). In turtle-graphics terms, \(F\) means “move forward one unit”, \(L\) and \(R\) mean quarter-turns, and the letters \(a\) and \(b\) are only structural markers: they do not move the turtle. After \(n\) substitution rounds, deleting \(a\) and \(b\) leaves the instruction word \(D_n\).
The task is to find the turtle's position after \(10^{12}\) forward moves in \(D_{50}\). The statement also provides a checkpoint: in \(D_{10}\), after 500 forward moves, the position is \((18,16)\). A direct expansion is impossible because \(D_{50}\) contains \(2^{50}\) forward moves, about \(1.13\times 10^{15}\), so the solution has to work with compressed recursive blocks rather than the full string.
The right object to precompute is not the text of a block, but its geometric effect. Every recursive block can be replaced by a small summary that records displacement, heading change, and the number of forward moves it contains. Once those summaries are known for all depths, the required position is a prefix query on a recursive grammar tree.
For any instruction block \(W\), define its summary by
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
where \(\vec v(W)=(\Delta x,\Delta y)\) is the net displacement, \(d(W)\in\{0,1,2,3\}\) is the net number of right turns modulo 4, and \(s(W)\) is the number of forward commands \(F\) inside \(W\).
If \(\operatorname{rot}(x,y)=(y,-x)\) denotes a \(90^\circ\) right rotation, then concatenation of two blocks is described by
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
for \(\Sigma_i=(\vec v_i,d_i,s_i)\). This is exactly the turtle rule: the second block must be interpreted in the heading left behind by the first block.
The atomic commands therefore have summaries
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
These vectors are written in the local frame of the block itself. When a stored block is later applied to the actual walk, its displacement is rotated by the current heading first and then added to the global position.
For clarity, let \(A_n\) and \(B_n\) denote the fully expanded instruction blocks produced by the two silent symbols after \(n\) remaining substitution levels, with empty base case
$$A_0=B_0=\varepsilon.$$
The substitution rules become the recurrences
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
The whole dragon word is then
$$D_n=F\,A_n.$$
Applying the composition law from the previous subsection gives
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
So every summary at depth \(n+1\) is built from a constant number of summaries at depth \(n\). This is the mathematical reason the preprocessing is linear in the order rather than exponential in the expanded word length.
Let \(f_n=s(A_n)=s(B_n)\). Both recursive definitions contain one explicit \(F\) and one copy each of the previous \(A_n\) and \(B_n\), so
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
Solving this recurrence gives
$$f_n=2^n-1.$$
Therefore \(D_n=F A_n\) contains exactly
$$1+f_n=2^n$$
forward moves. In particular, \(D_{50}\) has \(2^{50}\) forward steps, which is why explicit expansion is hopeless.
A second invariant concerns the final heading. If \(t_n=d(A_n)\) and \(u_n=d(B_n)\), then
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
with \(t_0=u_0=0\). From this it follows that
$$t_n=u_n=2\qquad (n\ge 1).$$
So every non-empty \(A_n\) or \(B_n\) turns the turtle around by \(180^\circ\). The implementations do not need a closed-form displacement formula, but this heading invariant is useful for understanding why the summaries compose so cleanly.
Suppose we only want the first \(K\) forward moves inside \(A_n\). If \(K\ge s(A_n)\), then the entire block lies inside the requested prefix, so one application of \(\Sigma(A_n)\) is enough. If \(K<s(A_n)\), then the desired prefix lies somewhere inside
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R,$$
and we process those pieces from left to right. The crucial detail is that the budget counts only forward moves. Turns are still applied when they occur before the \(K\)-th forward move, but they do not decrease the budget.
The same reasoning applies to \(B_n\). An induction on \(n\) shows that this recursive descent returns exactly the turtle state after the requested prefix. Structurally, at each depth there is at most one child block whose contribution is only partially used; everything before it can be swallowed whole from a precomputed summary, and everything after it is irrelevant once the budget reaches zero. That single-partial-branch invariant is what keeps the runtime linear in the order.
The first non-empty blocks are
$$A_1=RFR,\qquad B_1=LFL.$$
Using the local east-facing frame, their summaries are
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
At the next level,
$$A_2=A_1\,R\,B_1\,F\,R,$$
so
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
This already shows the compressed viewpoint at work: \(A_2\) contains three forward moves, but once its summary has been stored, those three moves can be consumed in one constant-time composition whenever the remaining budget covers them.
Since \(D_2=F A_2\), the whole word has \(2^2=4\) forward moves. Starting from the origin facing north, the initial \(F\) reaches \((0,1)\). If the remaining budget is 3, the entire \(A_2\) block can be applied at once. If the remaining budget were only 2, the algorithm would descend into \(A_1\), pass the explicit turn, and recurse only as far into \(B_1\) as the budget still allows. The actual \(10^{12}\)-step query uses exactly the same idea, just fifty levels deeper.
The C++, Python, and Java implementations allocate one stored summary for each depth of the \(A\)-family and the \(B\)-family. The deepest level is the empty block, and the tables are filled upward using the two recurrence formulas above. Each entry stores only four small pieces of data: displacement, net quarter-turn, and forward-step count.
Because the problem asks for \(D_{50}\), only 51 levels are needed. That makes the preprocessing tiny: the implementations never build the enormous string itself, only the summary tables for the recursive macros.
Execution starts at \((0,0)\) facing north, applies the initial \(F\), and then traverses the \(A\)-family recursively. Whenever the remaining forward-step budget covers an entire stored macro, the implementation subtracts that macro's step count and composes its summary into the current state in \(O(1)\).
If the budget does not cover the full macro, the implementation expands only that one macro level: it visits the child blocks in grammar order, applies turns immediately, and decreases the remaining budget only when a forward move is actually taken. The maintained invariant is simple and exact: after each recursive return, the stored global state equals the turtle state after the already processed prefix of forward moves.
All three languages implement the same mathematics. They also agree with the checkpoint from the statement: after 500 forward moves in \(D_{10}\), the position is \((18,16)\). That sanity check confirms both the summary-composition law and the prefix-recursion logic.
If the dragon order is \(n\), building all summaries for \(A_0,\dots,A_n\) and \(B_0,\dots,B_n\) costs \(O(n)\) time and \(O(n)\) memory. Each new level is obtained from a constant number of already known summaries.
Computing the position after one target prefix also costs \(O(n)\) time. The recursion may descend through all depths, but only one branch can remain partial at each level; every fully covered sibling is handled by a constant-time summary application. For Problem 220 this means the \(10^{12}\)-step query on \(D_{50}\) is solved with a few dozen summary compositions instead of expanding a word with \(2^{50}\) forward moves.
Die Heighway-Dragon-Kurve in dieser Aufgabe wird aus dem symbolischen Startwort \(D_0=Fa\) mit den Ersetzungen \(a\to aRbFR\) und \(b\to LFaLb\) erzeugt. In der Sprache der Turtle-Grafik bedeutet \(F\) „einen Schritt vorwärts“, \(L\) und \(R\) sind Vierteldrehungen, und die Buchstaben \(a\) und \(b\) sind nur Strukturmarker: Sie bewegen die Turtle nicht. Nach \(n\) Ersetzungsrunden erhält man \(D_n\), indem man anschließend \(a\) und \(b\) ignoriert.
Gesucht ist die Position nach \(10^{12}\) Vorwärtsschritten in \(D_{50}\). Die Aufgabenstellung liefert außerdem einen Kontrollpunkt: In \(D_{10}\) befindet sich die Turtle nach 500 Vorwärtsschritten bei \((18,16)\). Eine direkte Expansion ist ausgeschlossen, denn \(D_{50}\) enthält \(2^{50}\) Vorwärtsschritte, also etwa \(1{,}13\times 10^{15}\). Deshalb arbeitet die Lösung nicht mit der vollständigen Zeichenkette, sondern mit komprimierten rekursiven Blöcken.
Der richtige Vorverarbeitungsgegenstand ist nicht der Text eines Blocks, sondern seine geometrische Wirkung. Jeder rekursive Block wird durch eine kleine Zusammenfassung ersetzt, die Verschiebung, Richtungsänderung und Anzahl der Vorwärtsschritte speichert. Sind diese Zusammenfassungen für alle Tiefen bekannt, dann ist die gesuchte Position nur noch eine Präfixabfrage auf einem rekursiven Grammatikbaum.
Für jeden Befehlsblock \(W\) definieren wir seine Zusammenfassung durch
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
wobei \(\vec v(W)=(\Delta x,\Delta y)\) die Gesamtverschiebung ist, \(d(W)\in\{0,1,2,3\}\) die Nettoanzahl von Rechtsdrehungen modulo 4 und \(s(W)\) die Zahl der Vorwärtsbefehle \(F\) in \(W\).
Sei \(\operatorname{rot}(x,y)=(y,-x)\) die Drehung um \(90^\circ\) nach rechts. Dann gilt für die Verkettung zweier Blöcke
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
wenn \(\Sigma_i=(\vec v_i,d_i,s_i)\). Das ist genau die Turtle-Regel: Der zweite Block muss in der Richtung interpretiert werden, die der erste Block hinterlässt.
Die atomaren Befehle besitzen also die Zusammenfassungen
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
Diese Vektoren werden im lokalen Koordinatensystem des Blocks notiert. Wenn ein gespeicherter Block später auf den tatsächlichen Lauf angewandt wird, wird seine Verschiebung zunächst um die aktuelle Blickrichtung rotiert und erst dann zur globalen Position addiert.
Zur Übersicht bezeichnen wir mit \(A_n\) und \(B_n\) die vollständig expandierten Befehlsblöcke, die aus den beiden stillen Symbolen nach noch \(n\) Ersetzungsebenen entstehen, mit leerem Anfangsfall
$$A_0=B_0=\varepsilon.$$
Die Ersetzungsregeln werden damit zu den Rekurrenzen
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
Das gesamte Drachenwort ist dann
$$D_n=F\,A_n.$$
Mit der Verkettungsregel aus dem vorherigen Abschnitt folgt
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
Jede Zusammenfassung der Tiefe \(n+1\) entsteht also aus konstant vielen Zusammenfassungen der Tiefe \(n\). Genau deshalb ist die Vorverarbeitung nur linear in der Ordnung und nicht exponentiell in der Wortlänge.
Setze \(f_n=s(A_n)=s(B_n)\). Beide Rekursionen enthalten einen expliziten Vorwärtsschritt und je eine Kopie von \(A_n\) und \(B_n\), also
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
Daraus ergibt sich
$$f_n=2^n-1.$$
Folglich enthält \(D_n=F A_n\) genau
$$1+f_n=2^n$$
Vorwärtsschritte. Insbesondere besitzt \(D_{50}\) also \(2^{50}\) Schritte, weshalb explizite Expansion ausscheidet.
Eine zweite Invariante betrifft die Endrichtung. Schreibe \(t_n=d(A_n)\) und \(u_n=d(B_n)\). Dann gilt
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
mit \(t_0=u_0=0\). Daraus folgt
$$t_n=u_n=2\qquad (n\ge 1).$$
Jeder nichtleere \(A_n\)- oder \(B_n\)-Block dreht die Turtle also um \(180^\circ\) um. Die Implementierungen brauchen keine geschlossene Formel für die Verschiebung, aber diese Richtungsinvariante macht verständlich, warum sich die Zusammenfassungen so sauber zusammensetzen lassen.
Angenommen, wir wollen nur die ersten \(K\) Vorwärtsschritte innerhalb von \(A_n\). Falls \(K\ge s(A_n)\) gilt, liegt der gesamte Block im gewünschten Präfix, und eine einzige Anwendung von \(\Sigma(A_n)\) genügt. Falls \(K<s(A_n)\), liegt das Präfix irgendwo in
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R,$$
und wir verarbeiten diese Bestandteile von links nach rechts. Entscheidend ist, dass das Budget nur Vorwärtsschritte zählt. Drehungen werden trotzdem ausgeführt, wenn sie vor dem \(K\)-ten Vorwärtsschritt auftreten, aber sie verringern das Budget nicht.
Dasselbe Argument gilt für \(B_n\). Eine Induktion über \(n\) zeigt, dass dieser rekursive Abstieg exakt den Turtle-Zustand nach dem gewünschten Präfix liefert. Strukturell gibt es auf jeder Tiefe höchstens ein Kind, dessen Beitrag nur teilweise gebraucht wird; alles davor wird als vorberechnete Zusammenfassung ganz geschluckt, und alles danach ist irrelevant, sobald das Budget null ist. Genau diese „höchstens ein partieller Ast“-Invariante hält die Laufzeit linear in der Ordnung.
Die ersten nichtleeren Blöcke sind
$$A_1=RFR,\qquad B_1=LFL.$$
Im lokalen, nach Osten gerichteten Koordinatensystem haben sie die Zusammenfassungen
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
Auf der nächsten Ebene gilt
$$A_2=A_1\,R\,B_1\,F\,R,$$
also
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
Damit sieht man das komprimierte Denken bereits konkret: \(A_2\) enthält drei Vorwärtsschritte, aber sobald seine Zusammenfassung gespeichert ist, können diese drei Schritte in einer einzigen konstanten Komposition konsumiert werden, sofern das Restbudget sie vollständig umfasst.
Da \(D_2=F A_2\) gilt, besitzt das Gesamtwort \(2^2=4\) Vorwärtsschritte. Startet man im Ursprung mit Blick nach Norden, dann führt das erste \(F\) nach \((0,1)\). Ist das Restbudget gleich 3, kann der ganze \(A_2\)-Block sofort angewandt werden. Wäre das Restbudget nur 2, müsste der Algorithmus in \(A_1\) hinabsteigen, die explizite Drehung passieren und nur so weit in \(B_1\) hineinrekurrieren, wie es das Budget noch erlaubt. Genau derselbe Mechanismus arbeitet auch für die eigentliche Anfrage mit \(10^{12}\) Schritten, nur eben fünfzig Ebenen tief.
Die Implementierungen in C++, Python und Java legen für jede Tiefe der \(A\)-Familie und der \(B\)-Familie genau eine gespeicherte Zusammenfassung an. Die tiefste Ebene ist der leere Block, und die Tabellen werden nach oben mithilfe der beiden Rekursionsformeln aufgebaut. Jeder Eintrag speichert nur vier kleine Datenstücke: Verschiebung, Nettodrehung und Anzahl der Vorwärtsschritte.
Da die Aufgabe \(D_{50}\) verlangt, genügen 51 Ebenen. Die Vorverarbeitung ist daher winzig: Es wird niemals die gigantische Zeichenkette selbst erzeugt, sondern nur die Zusammenfassungstabelle der rekursiven Makros.
Die Ausführung beginnt bei \((0,0)\) mit Blick nach Norden, führt das anfängliche \(F\) aus und traversiert danach rekursiv die \(A\)-Familie. Immer dann, wenn das verbleibende Vorwärtsschrittbudget einen ganzen gespeicherten Makroblock umfasst, zieht die Implementierung dessen Schrittzahl ab und komponiert seine Zusammenfassung in \(O(1)\) in den aktuellen Zustand hinein.
Falls das Budget für den vollständigen Makroblock nicht reicht, expandiert die Implementierung nur diese eine Makroebene: Sie besucht die Kindblöcke in Grammatikreihenfolge, führt Drehungen sofort aus und reduziert das Budget nur dann, wenn tatsächlich ein Vorwärtsschritt gegangen wird. Die gepflegte Invariante ist einfach und exakt: Nach jeder rekursiven Rückkehr stimmt der gespeicherte globale Zustand genau mit dem Turtle-Zustand nach dem bereits abgearbeiteten Präfix von Vorwärtsschritten überein.
Alle drei Sprachen implementieren dieselbe Mathematik. Außerdem stimmen sie mit dem Kontrollpunkt aus der Aufgabenstellung überein: Nach 500 Vorwärtsschritten in \(D_{10}\) ist die Position \((18,16)\). Dieser Test bestätigt sowohl das Kompositionsgesetz der Zusammenfassungen als auch die Präfixrekursion.
Ist die Drachenordnung \(n\), dann kostet der Aufbau aller Zusammenfassungen für \(A_0,\dots,A_n\) und \(B_0,\dots,B_n\) genau \(O(n)\) Zeit und \(O(n)\) Speicher. Jede neue Ebene entsteht aus konstant vielen bereits bekannten Zusammenfassungen.
Auch die Berechnung der Position für ein einzelnes Zielpräfix kostet \(O(n)\) Zeit. Die Rekursion kann zwar bis zur vollen Tiefe hinabsteigen, aber auf jeder Ebene bleibt höchstens ein Ast partiell; jeder vollständig enthaltene Geschwisterast wird durch eine einzige konstante Zusammenfassung abgehandelt. Für Problem 220 bedeutet das: Die Anfrage „\(10^{12}\) Schritte in \(D_{50}\)“ wird mit wenigen Dutzend Zusammenfassungskompositionen gelöst, statt ein Wort mit \(2^{50}\) Vorwärtsschritten auszuschreiben.
Bu sorudaki Heighway Dragon, \(D_0=Fa\) başlangıcı ve \(a\to aRbFR\), \(b\to LFaLb\) dönüşümleriyle üretilir. Kaplumbağa grafiği açısından \(F\) “bir birim ileri git”, \(L\) ve \(R\) ise çeyrek dönüşlerdir; \(a\) ile \(b\) yalnızca yapısal işaretlerdir ve kaplumbağayı hareket ettirmez. \(n\) kez dönüşüm uygulandıktan sonra \(a\) ve \(b\) silinince \(D_n\) komut dizisi elde edilir.
İstenen, \(D_{50}\) içinde \(10^{12}\) ileri hareketten sonraki konumdur. Soru ayrıca bir kontrol noktası da verir: \(D_{10}\) içinde 500 ileri adımdan sonra konum \((18,16)\) olur. Doğrudan açılım mümkün değildir; çünkü \(D_{50}\) tam olarak \(2^{50}\) ileri adım içerir, yani yaklaşık \(1.13\times 10^{15}\). Bu yüzden çözüm, tüm diziyi üretmek yerine büyük özyinelemeli blokların sıkıştırılmış özetleriyle çalışır.
Önceden hesaplanması gereken şey bir bloğun metni değil, geometrik etkisidir. Her özyinelemeli blok, yer değiştirme, yön değişimi ve içerdiği ileri adım sayısını tutan küçük bir özetle temsil edilir. Bu özetler bütün derinlikler için hazır olunca, aranan konum aslında özyinelemeli bir gramer ağacı üzerinde bir ön-ek sorgusuna dönüşür.
Herhangi bir \(W\) komut bloğu için özetini
$$\Sigma(W)=(\vec v(W),d(W),s(W))$$
şeklinde tanımlayalım. Burada \(\vec v(W)=(\Delta x,\Delta y)\) net yer değiştirme, \(d(W)\in\{0,1,2,3\}\) mod 4 sağ dönüş sayısı ve \(s(W)\) de \(W\) içindeki ileri komutlarının sayısıdır.
\(\operatorname{rot}(x,y)=(y,-x)\) işlemi \(90^\circ\) sağ dönüşü göstersin. O zaman iki bloğun art arda uygulanması
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right)$$
yasasına uyar; burada \(\Sigma_i=(\vec v_i,d_i,s_i)\). Bu tam olarak kaplumbağa kuralıdır: ikinci blok, birinci bloğun bıraktığı yön içinde yorumlanmalıdır.
Dolayısıyla atomik komutların özetleri
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0)$$
olur. Bu vektörler bloğun kendi yerel koordinat sisteminde yazılır. Özet daha sonra gerçek yürüyüşe uygulanırken, yer değiştirme vektörü önce güncel yöne göre döndürülür, sonra global konuma eklenir.
Açıklığı artırmak için, iki sessiz sembolden doğan tam açılmış komut bloklarını \(A_n\) ve \(B_n\) ile gösterelim; burada \(n\), kalan dönüşüm seviyesidir. Başlangıç durumu boştur:
$$A_0=B_0=\varepsilon.$$
Böylece dönüşüm kuralları şu özyinelemelere dönüşür:
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
Tüm dragon komut dizisi ise
$$D_n=F\,A_n$$
şeklindedir. Bir önceki alt bölümdeki bileşim kuralı kullanılırsa
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n)$$
elde edilir. Yani derinlik \(n+1\) özeti, derinlik \(n\) özetlerinin sabit sayıda birleşiminden oluşur. Ön hesaplamanın üstel değil doğrusal olmasının sebebi budur.
\(f_n=s(A_n)=s(B_n)\) olsun. Her iki özyineleme de bir açık \(F\) komutu ve birer tane \(A_n\), \(B_n\) kopyası içerdiği için
$$f_{n+1}=2f_n+1,\qquad f_0=0$$
olur. Buradan
$$f_n=2^n-1$$
çıkar. Dolayısıyla \(D_n=F A_n\) tam olarak
$$1+f_n=2^n$$
ileri adım içerir. Özellikle \(D_{50}\) için bu sayı \(2^{50}\)'dir; tam açılımın imkansız olmasının nedeni de budur.
İkinci bir invariant, son yönle ilgilidir. \(t_n=d(A_n)\) ve \(u_n=d(B_n)\) tanımlarını yaparsak
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4$$
ve başlangıçta \(t_0=u_0=0\) elde edilir. Buradan
$$t_n=u_n=2\qquad (n\ge 1).$$
sonucu çıkar; yani boş olmayan her \(A_n\) veya \(B_n\) bloğu kaplumbağayı başladığı yöne göre \(180^\circ\) çevirir. Uygulamalar kapalı form yer değiştirme formülüne ihtiyaç duymaz, ama bu yön invariantı özetlerin neden bu kadar temiz birleştiğini açıklamak için faydalıdır.
Diyelim ki \(A_n\) içindeki ilk \(K\) ileri adıma ihtiyacımız var. Eğer \(K\ge s(A_n)\) ise, istenen ön-ek tüm bloğu kapsar ve \(\Sigma(A_n)\) özetini bir kez uygulamak yeterlidir. Eğer \(K<s(A_n)\) ise, aranan ön-ek şu açılımın bir yerindedir:
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R.$$
O zaman parçaları soldan sağa işleriz. Buradaki kritik nokta, bütçenin yalnızca ileri adımları saymasıdır. Dönüşler, eğer \(K\)-inci ileri adımdan önce geliyorsa uygulanır; fakat bütçeden düşmez.
Aynı mantık \(B_n\) için de geçerlidir. \(n\) üzerinde yapılan bir tümevarım, bu özyinelemeli inişin tam olarak istenen ön-ekten sonraki kaplumbağa durumunu verdiğini gösterir. Yapısal olarak her derinlikte katkısı yalnızca kısmen kullanılan en fazla bir çocuk blok vardır; ondan önceki her şey hazır özetle tek hamlede yutulur, ondan sonrası ise bütçe sıfıra indiği anda anlamsız hale gelir. Çalışma süresini doğrusal tutan şey bu “en fazla bir kısmi dal” invariantıdır.
İlk boş olmayan bloklar
$$A_1=RFR,\qquad B_1=LFL$$
şeklindedir. Yerel, doğuya bakan koordinat sisteminde özetleri
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1)$$
olur. Bir sonraki seviyede
$$A_2=A_1\,R\,B_1\,F\,R$$
ve dolayısıyla
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3)$$
elde edilir. Böylece sıkıştırılmış bakışın gücü hemen görülür: \(A_2\) üç ileri adım içerir, ama özeti hazır olduktan sonra bu üç adım tek bir sabit-zamanlı bileşimle tüketilebilir.
\(D_2=F A_2\) olduğundan tüm dizi \(2^2=4\) ileri adım içerir. Başlangıç noktası orijin ve başlangıç yönü kuzey ise, ilk \(F\) komutu kaplumbağayı \((0,1)\) noktasına taşır. Kalan bütçe 3 ise tüm \(A_2\) bloğu tek hamlede uygulanabilir. Kalan bütçe yalnızca 2 olsaydı, algoritma önce \(A_1\) içine iner, sonra açık dönüşü geçer ve yalnızca bütçenin izin verdiği kadar \(B_1\) içine girerdi. Gerçek \(10^{12}\) adım sorgusu da aynı fikri kullanır; tek fark derinliğin elli olmasıdır.
C++, Python ve Java uygulamaları, \(A\)-ailesi ve \(B\)-ailesinin her derinliği için birer özet saklar. En derin seviye boş bloktur; tablolar yukarı doğru, biraz önce verilen iki özyineleme formülü kullanılarak doldurulur. Her kayıt yalnızca dört küçük bilgi tutar: yer değiştirme, net çeyrek dönüş ve ileri adım sayısı.
Soruda \(D_{50}\) gerektiği için yalnızca 51 seviye yeterlidir. Bu nedenle ön işlem çok küçüktür: dev komut dizisinin kendisi asla üretilmez, yalnızca özyinelemeli makroların özet tablosu oluşturulur.
Çalıştırma \((0,0)\) noktasında kuzeye bakarak başlar, ilk \(F\) uygulanır ve sonra \(A\)-ailesi üzerinde özyinelemeli bir dolaşım yapılır. Kalan ileri adım bütçesi saklanan bir makronun tamamını kapsıyorsa, uygulama o makronun adım sayısını bütçeden düşer ve özetini mevcut duruma \(O(1)\) zamanda bileştirir.
Bütçe makronun tamamına yetmiyorsa, yalnızca o tek makro seviyesi açılır: çocuk bloklar gramer sırasıyla ziyaret edilir, dönüşler anında uygulanır ve bütçe sadece gerçekten bir ileri adım atıldığında azaltılır. Korunan invariant çok nettir: her özyinelemeli dönüşten sonra saklanan global durum, işlenmiş ileri-adım ön-ekinden sonraki gerçek kaplumbağa durumuna eşittir.
Üç dildeki uygulamaların matematiği aynıdır. Ayrıca hepsi sorudaki kontrol noktasını doğrular: \(D_{10}\) içinde 500 ileri adımdan sonra konum \((18,16)\) olur. Bu test, hem özet bileşim kuralını hem de ön-ek özyinelemesinin mantığını doğrular.
Dragon mertebesi \(n\) ise, \(A_0,\dots,A_n\) ve \(B_0,\dots,B_n\) için tüm özetleri kurmak \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Her yeni seviye, zaten bilinen sabit sayıda özetten elde edilir.
Tek bir hedef ön-ek için konumu hesaplamak da \(O(n)\) zamandır. Özyineleme tam derinliğe kadar inebilir; fakat her seviyede yalnızca bir dal kısmi kalabilir, tam kapsanan kardeşler ise tek bir sabit-zamanlı özet uygulamasıyla geçilir. Problem 220 için bu, \(D_{50}\) içinde \(10^{12}\) ileri adım sorgusunun, \(2^{50}\) adımlık bir diziyi açmadan, yalnızca birkaç düzine özet bileşimiyle çözüldüğü anlamına gelir.
La curva de Heighway Dragon de este problema se genera a partir de la palabra inicial \(D_0=Fa\) y de las sustituciones \(a\to aRbFR\) y \(b\to LFaLb\). En términos de turtle graphics, \(F\) significa “avanzar una unidad”, \(L\) y \(R\) son giros de un cuarto de vuelta, y las letras \(a\) y \(b\) son solo marcadores estructurales: no mueven a la tortuga. Después de \(n\) rondas de sustitución, al eliminar \(a\) y \(b\) queda la palabra de instrucciones \(D_n\).
Hay que encontrar la posición tras \(10^{12}\) movimientos hacia delante dentro de \(D_{50}\). El enunciado también da un punto de control: en \(D_{10}\), tras 500 avances, la posición es \((18,16)\). Expandir la cadena de forma directa es imposible, porque \(D_{50}\) contiene \(2^{50}\) avances, aproximadamente \(1.13\times 10^{15}\). Por eso la solución trabaja con bloques recursivos comprimidos en lugar de construir la palabra completa.
Lo que conviene precomputar no es el texto de cada bloque, sino su efecto geométrico. Cada bloque recursivo puede sustituirse por un resumen pequeño que almacena su desplazamiento, su cambio neto de orientación y el número de avances que contiene. Una vez conocidos esos resúmenes para todas las profundidades, la posición pedida se convierte en una consulta de prefijo sobre un árbol gramatical recursivo.
Para cualquier bloque de instrucciones \(W\), definimos su resumen por
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
donde \(\vec v(W)=(\Delta x,\Delta y)\) es el desplazamiento neto, \(d(W)\in\{0,1,2,3\}\) es el número neto de giros a la derecha módulo 4, y \(s(W)\) es la cantidad de comandos \(F\) contenidos en \(W\).
Si \(\operatorname{rot}(x,y)=(y,-x)\) denota una rotación de \(90^\circ\) hacia la derecha, entonces la concatenación de dos bloques satisface
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
para \(\Sigma_i=(\vec v_i,d_i,s_i)\). Esta es exactamente la regla de la tortuga: el segundo bloque debe interpretarse con la orientación dejada por el primero.
Por lo tanto, los comandos atómicos tienen los resúmenes
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
Estos vectores se guardan en el sistema de referencia local del propio bloque. Cuando más tarde se aplica un bloque almacenado al recorrido real, su desplazamiento se rota primero según la orientación actual y solo después se suma a la posición global.
Para fijar la notación, llamemos \(A_n\) y \(B_n\) a los bloques de instrucciones completamente expandidos que nacen de los dos símbolos mudos cuando quedan \(n\) niveles de sustitución, con caso base vacío
$$A_0=B_0=\varepsilon.$$
Las reglas de sustitución pasan a ser
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
La palabra completa del dragón es entonces
$$D_n=F\,A_n.$$
Al aplicar la ley de composición del apartado anterior se obtiene
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
Así, cada resumen de profundidad \(n+1\) se construye a partir de un número constante de resúmenes de profundidad \(n\). Esa es la razón matemática de que la preparación sea lineal en el orden y no exponencial en la longitud expandida.
Sea \(f_n=s(A_n)=s(B_n)\). Ambas recurrencias contienen un \(F\) explícito y una copia de \(A_n\) y \(B_n\), de modo que
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
La solución es
$$f_n=2^n-1.$$
Por consiguiente, \(D_n=F A_n\) contiene exactamente
$$1+f_n=2^n$$
movimientos hacia delante. En particular, \(D_{50}\) tiene \(2^{50}\) avances, y por eso la expansión completa es inviable.
Un segundo invariante describe la orientación final. Si escribimos \(t_n=d(A_n)\) y \(u_n=d(B_n)\), entonces
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
con \(t_0=u_0=0\). De aquí se deduce que
$$t_n=u_n=2\qquad (n\ge 1).$$
Es decir, cualquier bloque no vacío \(A_n\) o \(B_n\) deja a la tortuga mirando en la dirección opuesta a la inicial. Las implementaciones no necesitan una fórmula cerrada para el desplazamiento, pero este invariante de orientación ayuda a entender por qué los resúmenes se encajan tan bien.
Supongamos que solo queremos los primeros \(K\) avances dentro de \(A_n\). Si \(K\ge s(A_n)\), entonces todo el bloque cabe en el prefijo pedido y basta con aplicar una vez \(\Sigma(A_n)\). Si \(K<s(A_n)\), entonces el prefijo buscado cae en algún punto de
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R,$$
y procesamos esas piezas de izquierda a derecha. El detalle decisivo es que el presupuesto cuenta únicamente movimientos hacia delante. Los giros se siguen aplicando cuando aparecen antes del \(K\)-ésimo avance, pero no consumen presupuesto.
El mismo razonamiento vale para \(B_n\). Una inducción en \(n\) demuestra que este descenso recursivo devuelve exactamente el estado de la tortuga tras el prefijo solicitado. Estructuralmente, en cada profundidad hay a lo sumo un bloque hijo cuya contribución se usa solo parcialmente; todo lo que va antes se traga de una vez mediante un resumen precomputado, y todo lo que va después deja de importar en cuanto el presupuesto llega a cero. Ese invariante de “como mucho una rama parcial” es lo que mantiene el tiempo lineal en el orden.
Los primeros bloques no vacíos son
$$A_1=RFR,\qquad B_1=LFL.$$
En el sistema local orientado hacia el este, sus resúmenes son
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
En el siguiente nivel,
$$A_2=A_1\,R\,B_1\,F\,R,$$
y por tanto
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
Aquí ya se ve la idea comprimida en acción: \(A_2\) contiene tres avances, pero una vez almacenado su resumen, esos tres pasos pueden consumirse mediante una sola composición de tiempo constante siempre que el presupuesto restante los cubra por completo.
Como \(D_2=F A_2\), la palabra completa tiene \(2^2=4\) avances. Si empezamos en el origen mirando hacia el norte, el primer \(F\) lleva a \((0,1)\). Si el presupuesto restante es 3, todo el bloque \(A_2\) puede aplicarse de golpe. Si el presupuesto restante fuera solo 2, el algoritmo descendería dentro de \(A_1\), atravesaría el giro explícito y solo seguiría recursivamente dentro de \(B_1\) hasta donde el presupuesto lo permitiera. La consulta real de \(10^{12}\) pasos usa exactamente la misma idea, solo que cincuenta niveles más abajo.
Las implementaciones en C++, Python y Java reservan un resumen almacenado para cada profundidad de la familia \(A\) y de la familia \(B\). La profundidad más honda corresponde al bloque vacío, y las tablas se rellenan hacia arriba usando las dos recurrencias anteriores. Cada entrada almacena solo cuatro datos pequeños: desplazamiento, giro neto de cuarto de vuelta y cantidad de avances.
Como el problema pide \(D_{50}\), solo hacen falta 51 niveles. Eso vuelve diminuta la fase previa: las implementaciones nunca generan la palabra gigantesca, sino únicamente las tablas de resúmenes de los macros recursivos.
La ejecución comienza en \((0,0)\) mirando hacia el norte, aplica el \(F\) inicial y luego recorre recursivamente la familia \(A\). Siempre que el presupuesto restante de avances cubre un macro completo ya almacenado, la implementación resta el número de pasos de ese macro y compone su resumen en el estado actual en \(O(1)\).
Si el presupuesto no alcanza para el macro completo, la implementación expande solo ese nivel: visita los bloques hijos en el orden de la gramática, aplica los giros de inmediato y reduce el presupuesto únicamente cuando realmente consume un avance. El invariante mantenido es directo y exacto: tras cada retorno recursivo, el estado global almacenado coincide con el estado de la tortuga después del prefijo de avances ya procesado.
Los tres lenguajes implementan exactamente la misma matemática. Además, todos concuerdan con el punto de control del enunciado: después de 500 avances en \(D_{10}\), la posición es \((18,16)\). Esa comprobación valida tanto la ley de composición de resúmenes como la lógica del descenso por prefijos.
Si el orden del dragón es \(n\), construir todos los resúmenes de \(A_0,\dots,A_n\) y \(B_0,\dots,B_n\) cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Cada nuevo nivel se obtiene a partir de un número constante de resúmenes ya conocidos.
Calcular la posición para un único prefijo objetivo también cuesta \(O(n)\) tiempo. La recursión puede descender por toda la profundidad, pero en cada nivel solo una rama puede quedar parcial; cualquier hermano totalmente cubierto se procesa con una sola aplicación de resumen en tiempo constante. Para el Problema 220 esto significa que la consulta de \(10^{12}\) avances en \(D_{50}\) se resuelve con unas pocas decenas de composiciones, en lugar de expandir una palabra con \(2^{50}\) movimientos hacia delante.
本题中的 Heighway Dragon 由符号规则生成：起始词是 \(D_0=Fa\)，替换规则为 \(a\to aRbFR\) 与 \(b\to LFaLb\)。在海龟绘图的意义下，\(F\) 表示“向前走一格”，\(L\) 和 \(R\) 表示四分之一转，字母 \(a\) 与 \(b\) 只是结构占位符，本身不会让海龟移动。对这些规则做 \(n\) 轮替换之后，再把 \(a\) 和 \(b\) 删除，就得到真正执行的指令串 \(D_n\)。
要求的是：在 \(D_{50}\) 中执行完 \(10^{12}\) 次前进之后，海龟位于哪里。题目还给了一个校验点：在 \(D_{10}\) 中执行完 500 次前进后，位置应为 \((18,16)\)。显然不能直接把整条指令串展开，因为 \(D_{50}\) 恰好包含 \(2^{50}\) 次前进，约为 \(1.13\times 10^{15}\)。因此真正可行的做法不是处理完整字符串，而是对递归块做压缩总结。
这里最关键的抽象不是“一个很长的字符串”，而是“一个指令块对海龟状态造成的整体效果”。每个递归块都可以用一个很小的摘要来表示，里面记录净位移、净朝向变化，以及其中包含多少个前进命令。只要把所有深度对应的这些摘要预先算出来，题目就从“巨大字符串的模拟”变成了“递归语法树上的前缀查询”。
对任意指令块 \(W\)，定义它的摘要
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
其中 \(\vec v(W)=(\Delta x,\Delta y)\) 是净位移，\(d(W)\in\{0,1,2,3\}\) 表示净向右转的次数（模 4），\(s(W)\) 则表示 \(W\) 中前进命令 \(F\) 的总数。
记 \(\operatorname{rot}(x,y)=(y,-x)\) 为向右旋转 \(90^\circ\)。如果两个块顺次执行，对应的组合律就是
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
其中 \(\Sigma_i=(\vec v_i,d_i,s_i)\)。这正是海龟图形的真实规则：第二段路径必须在第一段留下的朝向中解释。
于是三个原子命令的摘要分别为
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
这些向量都写在该块自己的局部坐标系里。等到把一个预存的摘要真正作用到全局路径时，先按当前朝向把位移向量旋转，再把它加到全局位置上。
为了叙述清楚，记 \(A_n\) 和 \(B_n\) 为两个静默符号在还剩 \(n\) 层替换时所对应的完整展开块，空基例为
$$A_0=B_0=\varepsilon.$$
那么替换规则就等价于下面的递推：
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
而整条 Dragon 指令串就是
$$D_n=F\,A_n.$$
把上一小节的组合律代进去，就得到
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
这说明深度 \(n+1\) 的摘要只需要由常数个深度 \(n\) 的摘要合成出来即可，因此预处理成本是关于阶数的线性量，而不是关于展开后字符串长度的指数级量。
设 \(f_n=s(A_n)=s(B_n)\)。由于两条递推式都包含一个显式的 \(F\)，并各自包含一份 \(A_n\) 与 \(B_n\)，所以有
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
解出之后得到
$$f_n=2^n-1.$$
因此 \(D_n=F A_n\) 中前进命令的总数正好是
$$1+f_n=2^n.$$
特别地，\(D_{50}\) 含有 \(2^{50}\) 次前进，这就是为什么完整展开根本不现实。
另一个有用的不变量是块执行后的最终朝向。若记 \(t_n=d(A_n)\)、\(u_n=d(B_n)\)，则
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
且 \(t_0=u_0=0\)。由此可推出
$$t_n=u_n=2\qquad (n\ge 1).$$
也就是说，任何非空的 \(A_n\) 或 \(B_n\) 都会让海龟最终朝向与起始方向相反。实现并不需要位移的闭式公式，但这个朝向不变量能很好地解释为什么这些摘要可以如此自然地拼接起来。
假设我们只想知道 \(A_n\) 中前 \(K\) 次前进之后的状态。如果 \(K\ge s(A_n)\)，那就说明整个 \(A_n\) 都落在所需前缀内，此时直接应用一次 \(\Sigma(A_n)\) 即可。如果 \(K<s(A_n)\)，则目标前缀必然落在
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R$$
的某个位置上，于是按语法顺序从左到右处理这些部分。这里的关键细节是：预算只统计前进次数。转向命令如果出现在第 \(K\) 次前进之前，当然仍然会执行，但它们不会消耗预算。
对 \(B_n\) 也是同样的逻辑。对 \(n\) 做归纳即可证明：这种递归下降确实返回了“执行完指定数量前进之后”的精确海龟状态。更重要的结构事实是：在每一层深度上，至多只有一个子块会被“部分使用”；它左边的完整兄弟块都可以直接用预处理摘要一口吞掉，而一旦预算变成 0，右边的部分就完全不必再看。正是这个“每层至多一条部分分支”的性质，让算法时间保持在线性级别。
最先出现的非空块是
$$A_1=RFR,\qquad B_1=LFL.$$
在局部、面向东方的坐标系里，它们的摘要分别为
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
再往上一层，
$$A_2=A_1\,R\,B_1\,F\,R,$$
所以
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
这已经很好地展示了压缩思想：\(A_2\) 内部明明有 3 次前进，但一旦把这个摘要算好，只要剩余预算至少是 3，就能用一次常数时间的组合把整个块吃掉，而不必逐字符展开。
由于 \(D_2=F A_2\)，整条指令串一共有 \(2^2=4\) 次前进。若从原点朝北出发，最开始那个 \(F\) 会先把海龟带到 \((0,1)\)。如果此后剩余预算为 3，那么整个 \(A_2\) 就能被一次性应用；如果剩余预算只有 2，算法就会向下进入 \(A_1\)，越过那个显式右转，再只对 \(B_1\) 的前面一部分继续递归。真正的 \(10^{12}\) 步目标完全是同一个机制，只不过递归深度变成了 50。
C++、Python 和 Java 的实现都会为 \(A\) 家族和 \(B\) 家族的每一层深度各存一份摘要。最深层对应空块，然后利用上面的两个递推式自底向上填表。每个表项只包含四类很小的数据：位移、净四分之一转角以及前进步数。
由于题目只需要 \(D_{50}\)，所以总共只要 51 层。也因此，预处理本身非常小：实现从头到尾都不会构造那条庞大的真实指令串，只会构造这些递归宏的摘要表。
执行时从 \((0,0)\) 且朝北开始，先应用初始的 \(F\)，然后进入 \(A\) 家族做递归遍历。只要剩余的前进预算足以覆盖某个完整宏块，实现就直接减去这个块的步数，并在 \(O(1)\) 时间内把该摘要合成到当前状态里。
如果预算不足以覆盖整块，实现就只展开这一层：按语法顺序访问子块，转向立即生效，而预算只有在真正执行一次前进时才减少。整个过程中维护的核心不变量是：每次递归返回时，当前保存的全局状态都恰好等于“已经处理完的前进前缀”之后的真实海龟状态。
三种语言实现的数学内容完全一致。它们也都满足题目给出的校验点：在 \(D_{10}\) 中执行 500 次前进后，位置必须是 \((18,16)\)。这同时验证了摘要组合律与前缀递归逻辑。
若龙曲线的阶数为 \(n\)，那么构造 \(A_0,\dots,A_n\) 与 \(B_0,\dots,B_n\) 的全部摘要需要 \(O(n)\) 时间和 \(O(n)\) 空间。每一层新摘要都只由常数个旧摘要组合而成。
计算某一个目标前缀的位置同样只需 \(O(n)\) 时间。虽然递归可能一路下降到最底层，但在每一层上至多只有一条分支是“部分展开”的，其余被完整覆盖的兄弟块都可以通过一次常数时间的摘要应用直接处理。对于 Problem 220，这意味着在 \(D_{50}\) 中求第 \(10^{12}\) 次前进后的坐标，只需要几十次摘要组合，而不是展开含有 \(2^{50}\) 次前进的完整指令串。
Кривая Хейуэя в этой задаче порождается из начального слова \(D_0=Fa\) по правилам замены \(a\to aRbFR\) и \(b\to LFaLb\). В терминах turtle graphics команда \(F\) означает «сделать шаг вперед», \(L\) и \(R\) обозначают повороты на четверть оборота, а символы \(a\) и \(b\) служат только структурными метками и не двигают черепаху. После \(n\) раундов замен, если удалить \(a\) и \(b\), останется исполняемое слово \(D_n\).
Нужно найти положение после \(10^{12}\) шагов вперед в слове \(D_{50}\). В условии дан и контрольный пример: в \(D_{10}\) после 500 шагов вперед позиция равна \((18,16)\). Полностью развернуть слово невозможно, потому что \(D_{50}\) содержит \(2^{50}\) шагов вперед, то есть примерно \(1.13\times 10^{15}\). Поэтому решение работает не с явной строкой команд, а со сжатыми рекурсивными блоками.
Предвычислять нужно не текст блока, а его геометрический эффект. Каждый рекурсивный блок можно заменить компактной сводкой, в которой хранятся суммарное смещение, итоговое изменение направления и число команд \(F\). Когда такие сводки известны для всех глубин, искомая позиция превращается в задачу о префиксе на рекурсивном дереве грамматики.
Для любого блока команд \(W\) определим его сводку как
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
где \(\vec v(W)=(\Delta x,\Delta y)\) есть суммарное смещение, \(d(W)\in\{0,1,2,3\}\) есть суммарное число правых поворотов по модулю 4, а \(s(W)\) равно числу команд движения вперед внутри \(W\).
Пусть \(\operatorname{rot}(x,y)=(y,-x)\) обозначает поворот на \(90^\circ\) вправо. Тогда конкатенация двух блоков описывается формулой
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
где \(\Sigma_i=(\vec v_i,d_i,s_i)\). Это в точности правило черепахи: второй блок нужно интерпретировать в том направлении, которое оставил после себя первый.
Следовательно, атомарные команды имеют сводки
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
Эти векторы записываются в локальной системе координат самого блока. Когда потом готовый блок применяется к реальному пути, его смещение сначала поворачивается в соответствии с текущим направлением, а уже затем добавляется к глобальной позиции.
Для удобства обозначим через \(A_n\) и \(B_n\) полностью развернутые блоки, порождаемые двумя немыми символами при еще \(n\) оставшихся уровнях замен. Базовый случай пуст:
$$A_0=B_0=\varepsilon.$$
Тогда правила замены переписываются как рекуррентные соотношения
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
Полное слово дракона равно
$$D_n=F\,A_n.$$
Применяя закон композиции из предыдущего пункта, получаем
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
Итак, каждая сводка глубины \(n+1\) строится из постоянного числа сводок глубины \(n\). Именно поэтому предварительная обработка линейна по порядку, а не экспоненциальна по длине развернутого слова.
Положим \(f_n=s(A_n)=s(B_n)\). В обеих рекурсиях есть один явный символ \(F\) и по одной копии \(A_n\) и \(B_n\), поэтому
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
Отсюда следует
$$f_n=2^n-1.$$
Следовательно, слово \(D_n=F A_n\) содержит ровно
$$1+f_n=2^n$$
шагов вперед. В частности, для \(D_{50}\) это \(2^{50}\), и именно поэтому полное развертывание не подходит.
Второй инвариант касается конечного направления. Если обозначить \(t_n=d(A_n)\) и \(u_n=d(B_n)\), то
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
при \(t_0=u_0=0\). Из этого получается
$$t_n=u_n=2\qquad (n\ge 1).$$
То есть любой непустой блок \(A_n\) или \(B_n\) разворачивает черепаху на \(180^\circ\). Реализациям не нужна замкнутая формула для смещения, но этот инвариант направления хорошо объясняет, почему сводки соединяются столь естественно.
Предположим, что нужны только первые \(K\) шагов вперед внутри \(A_n\). Если \(K\ge s(A_n)\), то весь блок входит в искомый префикс, и достаточно один раз применить \(\Sigma(A_n)\). Если же \(K<s(A_n)\), то интересующий префикс лежит где-то внутри
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R,$$
и тогда эти части обрабатываются слева направо. Принципиально важно, что бюджет считает только шаги вперед. Повороты выполняются, если они стоят до \(K\)-го движения вперед, но бюджет при этом не уменьшается.
Для \(B_n\) действует тот же принцип. Индукция по \(n\) показывает, что такой рекурсивный спуск дает в точности состояние черепахи после нужного префикса. Структурно на каждой глубине существует не более одного дочернего блока, который используется лишь частично; все, что стоит перед ним, поглощается целиком одной заранее вычисленной сводкой, а все, что стоит после него, перестает иметь значение, как только бюджет становится нулевым. Именно этот инвариант «не более одной частичной ветви на уровень» и обеспечивает линейное время работы.
Первые непустые блоки имеют вид
$$A_1=RFR,\qquad B_1=LFL.$$
В локальной системе координат, ориентированной на восток, их сводки равны
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
На следующем уровне
$$A_2=A_1\,R\,B_1\,F\,R,$$
поэтому
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
Здесь уже хорошо видно преимущество сжатого представления: внутри \(A_2\) есть три шага вперед, но как только его сводка посчитана, эти три шага можно поглотить одной операцией постоянного времени, если оставшийся бюджет их целиком покрывает.
Поскольку \(D_2=F A_2\), полное слово содержит \(2^2=4\) шага вперед. Если стартовать из начала координат лицом на север, то первый символ \(F\) переводит черепаху в точку \((0,1)\). Если после этого осталось 3 шага бюджета, весь блок \(A_2\) можно применить сразу. Если бы бюджета оставалось только 2, алгоритм спустился бы в \(A_1\), прошел бы явный поворот и рекурсировал бы в \(B_1\) лишь настолько, насколько позволяют оставшиеся шаги. Запрос для \(10^{12}\) шагов использует в точности ту же идею, только на глубине 50.
Реализации на C++, Python и Java хранят по одной сводке для каждой глубины семейства \(A\) и семейства \(B\). Самая глубокая запись соответствует пустому блоку, а затем таблицы заполняются снизу вверх по двум рекуррентным формулам выше. В каждой записи находится только четыре небольших величины: смещение, суммарный четверть-поворот и число шагов вперед.
Так как в задаче требуется \(D_{50}\), достаточно всего 51 уровня. Поэтому этап подготовки очень мал: реализации никогда не строят гигантскую строку команд, а строят только таблицы сводок рекурсивных макросов.
Исполнение начинается в точке \((0,0)\) с направлением на север, затем выполняется начальный \(F\), а после этого запускается рекурсивный обход семейства \(A\). Всякий раз, когда оставшийся бюджет шагов вперед покрывает целый сохраненный макроблок, реализация вычитает число его шагов и компонирует его сводку с текущим состоянием за \(O(1)\).
Если бюджета не хватает на весь макроблок, реализация раскрывает только этот уровень: дочерние части посещаются в грамматическом порядке, повороты применяются сразу, а бюджет уменьшается только в момент реального движения вперед. Поддерживаемый инвариант формулируется просто: после каждого возврата из рекурсии сохраненное глобальное состояние точно совпадает с состоянием черепахи после уже обработанного префикса шагов вперед.
Во всех трех языках реализована одна и та же математика. Кроме того, все версии согласуются с контрольной точкой из условия: после 500 шагов вперед в \(D_{10}\) позиция должна быть \((18,16)\). Эта проверка подтверждает и закон композиции сводок, и корректность префиксной рекурсии.
Если порядок дракона равен \(n\), то построение всех сводок для \(A_0,\dots,A_n\) и \(B_0,\dots,B_n\) требует \(O(n)\) времени и \(O(n)\) памяти. Каждый новый уровень строится из постоянного числа уже известных сводок.
Вычисление позиции для одного целевого префикса тоже стоит \(O(n)\) времени. Рекурсия может спуститься на всю глубину, но на каждом уровне частичной остается не более одной ветви; любой полностью покрытый сосед обрабатывается одной константной операцией применения сводки. Для Problem 220 это означает, что запрос «позиция после \(10^{12}\) шагов вперед в \(D_{50}\)» решается несколькими десятками композиций сводок вместо развертывания слова длины \(2^{50}\) по числу шагов.
منحنى Heighway Dragon في هذه المسألة يُولَّد انطلاقًا من الكلمة الابتدائية \(D_0=Fa\) مع قاعدتي الاستبدال \(a\to aRbFR\) و\(b\to LFaLb\). بلغة الرسم بالسلحفاة، يعبّر \(F\) عن خطوة واحدة إلى الأمام، ويمثل \(L\) و\(R\) ربع دورة، أما الحرفان \(a\) و\(b\) فهما مجرد رمزين بنيويين لا يحرّكان السلحفاة. بعد تطبيق الاستبدال \(n\) مرة، ثم حذف \(a\) و\(b\)، نحصل على سلسلة التعليمات الفعلية \(D_n\).
المطلوب هو تحديد موضع السلحفاة بعد \(10^{12}\) خطوة أمامية داخل \(D_{50}\). ويعطي نص المسألة أيضًا نقطة تحقق: في \(D_{10}\)، بعد 500 خطوة أمامية، يكون الموضع \((18,16)\). لا يمكن التوسيع المباشر لأن \(D_{50}\) يحتوي على \(2^{50}\) خطوة أمامية، أي نحو \(1.13\times 10^{15}\). لذلك لا بد من العمل بملخصات مضغوطة للكتل التكرارية بدل إنشاء السلسلة كاملة.
الشيء الصحيح الذي ينبغي حسابه مسبقًا ليس نص كل كتلة، بل أثرها الهندسي الصافي. فكل كتلة تكرارية يمكن استبدالها بملخص صغير يخزن الإزاحة الصافية، وتغير الاتجاه الصافي، وعدد أوامر التقدم التي تحتويها. وما إن تصبح هذه الملخصات معروفة لكل الأعماق، حتى تتحول المسألة إلى استعلام بادئة على شجرة قواعد تكرارية.
لكل كتلة تعليمات \(W\) نعرّف ملخصها كما يلي:
$$\Sigma(W)=(\vec v(W),d(W),s(W)),$$
حيث \(\vec v(W)=(\Delta x,\Delta y)\) هي الإزاحة الصافية، و\(d(W)\in\{0,1,2,3\}\) هو عدد الانعطافات إلى اليمين بترديد 4، و\(s(W)\) هو عدد أوامر التقدم \(F\) داخل \(W\).
إذا رمزنا بـ \(\operatorname{rot}(x,y)=(y,-x)\) إلى دوران مقداره \(90^\circ\) إلى اليمين، فإن ضم كتلتين متتاليتين يحقق العلاقة
$$\Sigma_1\star\Sigma_2=\left(\vec v_1+\operatorname{rot}^{d_1}(\vec v_2),\ (d_1+d_2)\bmod 4,\ s_1+s_2\right),$$
حيث \(\Sigma_i=(\vec v_i,d_i,s_i)\). وهذا يطابق تمامًا قاعدة السلحفاة: فالكتلة الثانية يجب تفسيرها في الاتجاه الذي تركته الكتلة الأولى.
ومن ثم تكون ملخصات الأوامر الذرية هي
$$\Sigma(F)=((1,0),0,1),\qquad \Sigma(R)=((0,0),1,0),\qquad \Sigma(L)=((0,0),3,0).$$
هذه المتجهات مكتوبة في الإطار المحلي للكتلة نفسها. وعندما نطبق لاحقًا كتلة مخزنة على المسار الحقيقي، فإننا ندوّر متجه الإزاحة أولًا بحسب الاتجاه الحالي، ثم نضيفه إلى الموضع العام.
لتسهيل الشرح، لِنُسمِّ \(A_n\) و\(B_n\) الكتلتين الناتجتين من الرمزين الصامتين عندما يتبقى \(n\) مستويات من الاستبدال، مع حالة أساس فارغة:
$$A_0=B_0=\varepsilon.$$
عندئذ تصبح قواعد الاستبدال هي العلاقتين
$$A_{n+1}=A_n\,R\,B_n\,F\,R,\qquad B_{n+1}=L\,F\,A_n\,L\,B_n.$$
أما الكلمة الكاملة للتنين فهي
$$D_n=F\,A_n.$$
وبتطبيق قانون التركيب السابق نحصل على
$$\Sigma(A_{n+1})=\Sigma(A_n)\star\Sigma(R)\star\Sigma(B_n)\star\Sigma(F)\star\Sigma(R),$$
$$\Sigma(B_{n+1})=\Sigma(L)\star\Sigma(F)\star\Sigma(A_n)\star\Sigma(L)\star\Sigma(B_n).$$
وهذا يعني أن كل ملخص في العمق \(n+1\) يُبنى من عدد ثابت من الملخصات في العمق \(n\). لهذا السبب تكون مرحلة التهيئة خطية في الرتبة، لا أسية في طول السلسلة بعد التوسيع.
لنكتب \(f_n=s(A_n)=s(B_n)\). كل من العلاقتين التكراريتين يحتوي على أمر \(F\) صريح وعلى نسخة من \(A_n\) ونسخة من \(B_n\)، ولذلك
$$f_{n+1}=2f_n+1,\qquad f_0=0.$$
ومنها نحصل على
$$f_n=2^n-1.$$
إذن الكلمة \(D_n=F A_n\) تحتوي بالضبط على
$$1+f_n=2^n$$
خطوة أمامية. وعلى وجه الخصوص فإن \(D_{50}\) يملك \(2^{50}\) خطوة أمامية، وهذا هو سبب استحالة التوسيع الصريح.
هناك ثابت ثانٍ مهم يتعلق بالاتجاه النهائي. إذا وضعنا \(t_n=d(A_n)\) و\(u_n=d(B_n)\)، فسنحصل على
$$t_{n+1}\equiv t_n+1+u_n+1 \pmod 4,\qquad u_{n+1}\equiv 3+t_n+3+u_n \pmod 4,$$
مع \(t_0=u_0=0\). ومن ثم ينتج
$$t_n=u_n=2\qquad (n\ge 1).$$
أي إن كل كتلة غير فارغة من النوع \(A_n\) أو \(B_n\) تجعل السلحفاة تنتهي وهي تنظر في الاتجاه المعاكس تمامًا للبداية. لا تحتاج التطبيقات إلى صيغة مغلقة للإزاحة، لكن هذا الثابت الخاص بالاتجاه يوضح لماذا تتراكب الملخصات بهذه السهولة.
افترض أننا نريد فقط أول \(K\) خطوة أمامية داخل \(A_n\). إذا كان \(K\ge s(A_n)\)، فإن الكتلة كلها تقع داخل البادئة المطلوبة، ويكفي تطبيق \(\Sigma(A_n)\) مرة واحدة. أما إذا كان \(K<s(A_n)\)، فإن البادئة المطلوبة تقع داخل
$$A_n=A_{n-1}\,R\,B_{n-1}\,F\,R,$$
وعندها نعالج هذه الأجزاء من اليسار إلى اليمين. والتفصيل الحاسم هنا هو أن الميزانية تعدّ الخطوات الأمامية فقط. فالانعطافات تُنفَّذ إذا ظهرت قبل الخطوة الأمامية رقم \(K\)، لكنها لا تُنقِص الميزانية.
والمنطق نفسه ينطبق على \(B_n\). وباستقراء على \(n\) نحصل على أن هذا الهبوط التكراري يعيد بدقة حالة السلحفاة بعد البادئة المطلوبة. ومن الناحية البنيوية، يوجد في كل عمق على الأكثر ابن واحد يُستخدم جزئيًا فقط؛ وكل ما قبله يُمتص دفعة واحدة بواسطة ملخص محسوب مسبقًا، وكل ما بعده يصبح غير مهم بمجرد وصول الميزانية إلى الصفر. هذا الثابت، أي «وجود فرع جزئي واحد على الأكثر في كل مستوى»، هو ما يجعل الزمن خطيًا في الرتبة.
أول الكتل غير الفارغة هي
$$A_1=RFR,\qquad B_1=LFL.$$
وفي الإطار المحلي المواجه للشرق تكون ملخصاتهما
$$\Sigma(A_1)=((0,-1),2,1),\qquad \Sigma(B_1)=((0,1),2,1).$$
وفي المستوى التالي
$$A_2=A_1\,R\,B_1\,F\,R,$$
ومن ثم
$$\Sigma(A_2)=\Sigma(A_1)\star\Sigma(R)\star\Sigma(B_1)\star\Sigma(F)\star\Sigma(R)=((-1,-2),2,3).$$
وهنا يظهر جوهر الضغط بوضوح: فداخل \(A_2\) ثلاث خطوات أمامية، لكن بعد حساب هذا الملخص يمكن استهلاك الخطوات الثلاث بتركيب ثابت الزمن واحد، ما دامت الميزانية المتبقية تغطيها بالكامل.
وبما أن \(D_2=F A_2\)، فإن الكلمة كلها تحتوي على \(2^2=4\) خطوات أمامية. إذا بدأنا من الأصل والسلحفاة تواجه الشمال، فإن \(F\) الأول ينقلها إلى \((0,1)\). وإذا كانت الميزانية المتبقية 3، أمكن تطبيق كتلة \(A_2\) كلها دفعة واحدة. أما إذا كانت الميزانية المتبقية 2 فقط، فإن الخوارزمية تهبط داخل \(A_1\)، ثم تعبر الانعطاف الصريح، ثم تتابع التكرار داخل \(B_1\) بمقدار ما تسمح به الميزانية. والاستعلام الحقيقي عند \(10^{12}\) خطوة يستخدم الفكرة نفسها تمامًا، لكنه أعمق بخمسين مستوى.
تُنشئ تطبيقات C++ وPython وJava ملخصًا مخزنًا لكل عمق من عائلة \(A\) وعائلة \(B\). أعمق مستوى يمثل الكتلة الفارغة، ثم تُملأ الجداول صعودًا باستخدام العلاقتين التكراريتين السابقتين. كل إدخال يخزن فقط أربع قطع صغيرة من البيانات: الإزاحة، والانعطاف الصافي بربع دورة، وعدد الخطوات الأمامية.
ولأن المسألة تطلب \(D_{50}\)، فعدد المستويات المطلوبة هو 51 فقط. لذلك تكون التهيئة صغيرة جدًا: التطبيقات لا تبني أبدًا السلسلة الهائلة نفسها، بل تبني فقط جداول ملخصات الماكروات التكرارية.
يبدأ التنفيذ من \((0,0)\) مع اتجاه ابتدائي نحو الشمال، ثم يُطبَّق الأمر \(F\) الأول، وبعد ذلك يبدأ الاجتياز التكراري داخل عائلة \(A\). وكلما كانت ميزانية الخطوات الأمامية المتبقية تكفي لتغطية ماكرو كامل مخزن مسبقًا، تطرح الشيفرة عدد خطوات ذلك الماكرو ثم تركب ملخصه في الحالة الحالية بزمن \(O(1)\).
أما إذا لم تكفِ الميزانية للماكرو كاملًا، فإن الشيفرة توسع ذلك المستوى فقط: تزور الأبناء بترتيب القواعد، وتطبق الانعطافات فورًا، ولا تنقص الميزانية إلا عندما تُستهلك خطوة أمامية فعلية. والثابت الذي يُحافَظ عليه واضح ودقيق: بعد كل عودة من الاستدعاء التكراري، تكون الحالة العامة المخزنة مساوية تمامًا لحالة السلحفاة بعد البادئة التي جرت معالجتها من الخطوات الأمامية.
اللغات الثلاث تنفذ الرياضيات نفسها تمامًا. كما أنها تتفق جميعًا مع نقطة التحقق الواردة في نص المسألة: بعد 500 خطوة أمامية في \(D_{10}\)، يجب أن يكون الموضع \((18,16)\). وهذا يثبت صحة كل من قانون تركيب الملخصات ومنطق التكرار على البادئات.
إذا كانت رتبة التنين هي \(n\)، فإن بناء جميع الملخصات لـ \(A_0,\dots,A_n\) و\(B_0,\dots,B_n\) يحتاج إلى \(O(n)\) زمنًا و\(O(n)\) ذاكرة. فكل مستوى جديد يُشتق من عدد ثابت من الملخصات المعروفة سابقًا.
كما أن حساب الموضع لبادئة مستهدفة واحدة يكلف أيضًا \(O(n)\) زمنًا. صحيح أن التكرار قد يهبط إلى العمق الكامل، لكن في كل مستوى لا يبقى جزئيًا إلا فرع واحد على الأكثر؛ أما كل الأخوة المغطاة بالكامل فيُعالجون بتطبيق ملخص واحد بزمن ثابت. وبالنسبة إلى Problem 220 فهذا يعني أن استعلام \(10^{12}\) خطوة أمامية داخل \(D_{50}\) يُحل ببضع عشرات من عمليات التركيب فقط، بدل توسيع كلمة تحتوي على \(2^{50}\) خطوة أمامية.