We start with two fixed 100-digit strings \(A\) and \(B\). From them we define Fibonacci words by
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
where juxtaposition means concatenation. The words grow extremely quickly, so the task is not to build them explicitly, but to recover individual digits at carefully chosen positions.
For a positive integer \(t\), let \(L_k=|F_k|\) and let \(k(t)\) be the smallest index such that \(L_{k(t)}\ge t\). The queried digit \(D_{A,B}(t)\) is the \(t\)-th digit of that first Fibonacci word long enough to contain position \(t\). The required answer is
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
The largest queried position is \(450\cdot 7^{17}=104683731294243150\), so any method that tries to construct the word itself is hopeless. The solution works entirely with lengths and index transformations.
The key observation is that a position inside a concatenated word can be traced back to exactly one position in a smaller word. Repeating that idea turns a gigantic string problem into a short descent through a Fibonacci-style length table.
If \(L_k=|F_k|\), then concatenation immediately gives
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
So the lengths follow the same recurrence as Fibonacci numbers. If \(f_1=f_2=1\) and \(f_k=f_{k-2}+f_{k-1}\), then
$$L_k=100f_k.$$
This matters because the algorithm never needs the words themselves. It only needs enough length values to know which block contains the target position. Since Fibonacci growth is exponential in \(k\), the largest required index is already covered by \(F_{74}\), so only a few dozen length values are needed.
Suppose we want the \(t\)-th digit of \(F_k\) with \(k\ge 3\). Because
$$F_k=F_{k-2}F_{k-1},$$
the first \(L_{k-2}\) positions of \(F_k\) come from \(F_{k-2}\), and the remaining \(L_{k-1}\) positions come from \(F_{k-1}\). Therefore the desired digit satisfies
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
This is the whole mathematics of the problem. One comparison with \(L_{k-2}\) tells us whether the target digit sits in the left block or the right block, and in the right-block case the local position is obtained by subtracting the entire left-block length.
Start from \(k=k(t)\), the smallest index with \(L_k\ge t\). At every stage, the state \((k,t)\) means: “the answer is the \(t\)-th digit of \(F_k\).” The descent rule preserves this statement exactly while making \(k\) smaller.
If the position lies in the left block, we replace \((k,t)\) by \((k-2,t)\). If it lies in the right block, we replace \((k,t)\) by \((k-1,t-L_{k-2})\). Either way, the word index drops, so after finitely many steps we must land at \(k=1\) or \(k=2\). At that point the answer is read directly from the seed string \(A\) or \(B\).
No branching tree is explored. For each query there is exactly one valid path downward through the concatenation structure.
Using the shorter seeds from the problem statement,
$$A=1415926535,\qquad B=8979323846,$$
the lengths are \(10,10,20,30,50,\dots\). The first Fibonacci word long enough to contain position \(35\) is \(F_5\), because \(L_4=30<35\le 50=L_5\).
Now apply the descent rule:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
The reasoning is
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
So the required digit is the 5th digit of \(A\), namely \(9\). This example shows exactly how an apparently large position collapses to a direct lookup in a base word.
For the actual problem, define
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
Each \(p_n\) is handled independently: find \(D_{A,B}(p_n)\) by descent, then place that digit at decimal weight \(10^n\). The final answer is therefore assembled as
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
The hard-looking global problem is thus just eighteen small position queries plus a decimal accumulation.
The C++, Python, and Java implementations store the two seed strings and generate the length sequence \(L_k\) iteratively. For each query they extend that table until the last length is at least the requested position. Because the largest query is reached by \(F_{74}\), this table remains tiny.
Once the relevant \(k\) is known, the implementation loops while \(k>2\). At each iteration it compares the current position with \(L_{k-2}\). A position in the left block keeps the same local index and jumps to \(F_{k-2}\); a position in the right block subtracts \(L_{k-2}\) and jumps to \(F_{k-1}\). When the loop reaches \(F_1\) or \(F_2\), the code reads the corresponding digit directly from \(A\) or \(B\).
The only indexing subtlety is that the mathematics is 1-indexed, while programming strings are 0-indexed. So the final character access uses position \(t-1\) inside the chosen seed.
After each digit extraction, the implementation adds it to a running total with weight \(10^n\). The three language versions follow the same sequence of eighteen queries and the same recurrence logic; they differ only in the numeric container used for the final accumulator.
If \(k(t)\) is the smallest index with \(L_{k(t)}\ge t\), then a single query performs one descent step per level until it reaches a seed. Its running time is therefore \(O(k(t))\). Since \(L_k=100f_k\) and Fibonacci numbers satisfy \(f_k=\Theta(\varphi^k)\), this is \(O(\log t)\).
For Problem 230 there are only 18 queries, and even the largest one starts at \(k=74\). So the full computation is only a few hundred simple integer operations. Memory usage is \(O(k_{\max})\) for the length table, which here means only a few dozen 64-bit values.
Aus zwei festen 100-stelligen Strings \(A\) und \(B\) werden Fibonacci-Wörter definiert durch
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
wobei die Nebeneinanderschreibung die Konkatenation bezeichnet. Die Wörter wachsen so schnell, dass man sie nicht explizit erzeugen darf; gesucht sind nur einzelne Ziffern an sehr großen Positionen.
Für ein positives \(t\) sei \(L_k=|F_k|\), und \(k(t)\) sei der kleinste Index mit \(L_{k(t)}\ge t\). Dann ist \(D_{A,B}(t)\) die \(t\)-te Ziffer des ersten Fibonacci-Wortes, das lang genug für diese Position ist. Gesucht wird also
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
Die größte abgefragte Position ist \(450\cdot 7^{17}=104683731294243150\). Ein direktes Konstruieren des Wortes ist daher ausgeschlossen; die Lösung arbeitet nur mit Längen und Positionsabbildungen.
Die zentrale Idee ist, eine Position in einem verketteten Wort auf genau eine Position in einem kleineren Wort zurückzuführen. Wiederholt man diesen Schritt, bleibt am Ende nur ein kurzer Abstieg durch eine Tabelle von Fibonacci-Längen.
Mit \(L_k=|F_k|\) folgt aus der Konkatenation sofort
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
Damit gehorchen die Längen derselben Rekursion wie die Fibonacci-Zahlen. Schreibt man \(f_1=f_2=1\) und \(f_k=f_{k-2}+f_{k-1}\), dann gilt
$$L_k=100f_k.$$
Genau das macht das Problem handhabbar: Man braucht nie die Wörter selbst, sondern nur genug Längenwerte, um den Zielindex in den linken oder rechten Block einzuordnen. Wegen des exponentiellen Wachstums reicht für die größte Anfrage schon \(F_{74}\), also eine sehr kleine Längentabelle.
Gesucht sei die \(t\)-te Ziffer von \(F_k\) mit \(k\ge 3\). Da
$$F_k=F_{k-2}F_{k-1},$$
stammen die ersten \(L_{k-2}\) Positionen aus \(F_{k-2}\), und die restlichen \(L_{k-1}\) Positionen stammen aus \(F_{k-1}\). Deshalb gilt
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
Das ist die eigentliche Kernformel. Ein einziger Vergleich mit \(L_{k-2}\) entscheidet, in welchem Teilwort die gesuchte Ziffer liegt, und im rechten Fall verschiebt man den Index um die gesamte Länge des linken Blocks.
Man beginnt bei \(k=k(t)\), also beim kleinsten Index mit \(L_k\ge t\). In jedem Schritt bedeutet der Zustand \((k,t)\): „Die gesuchte Ziffer ist die \(t\)-te Ziffer von \(F_k\).“ Die Abstiegsregel erhält diese Aussage exakt, verkleinert aber den Wortindex.
Liegt die Position im linken Block, wird \((k,t)\) durch \((k-2,t)\) ersetzt. Liegt sie im rechten Block, wird \((k,t)\) durch \((k-1,t-L_{k-2})\) ersetzt. In beiden Fällen sinkt \(k\), also endet der Prozess zwangsläufig bei \(F_1\) oder \(F_2\). Dort liest man die Ziffer direkt aus \(A\) oder \(B\) ab.
Es wird also kein Verzweigungsbaum verfolgt. Für jede Anfrage gibt es genau einen gültigen Pfad nach unten durch die Konkatenationsstruktur.
Mit den kürzeren Startstrings aus der Aufgabenstellung,
$$A=1415926535,\qquad B=8979323846,$$
sind die Längen \(10,10,20,30,50,\dots\). Das erste Fibonacci-Wort, das Position \(35\) enthält, ist \(F_5\), denn \(L_4=30<35\le 50=L_5\).
Nun wird die Abstiegsregel angewendet:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
Die Begründung lautet
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
Damit ist die gesuchte Ziffer die 5. Ziffer von \(A\), also \(9\). Genau dieses Beispiel wird von den Implementierungen als Plausibilitätskontrolle reproduziert.
Für das eigentliche Problem definiert man
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
Jedes \(p_n\) wird unabhängig behandelt: Berechne \(D_{A,B}(p_n)\) durch den beschriebenen Abstieg und setze die gefundene Ziffer mit Gewicht \(10^n\) in die Endsumme ein. Somit lautet die gesuchte Zahl
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
Das globale Problem zerfällt also in nur 18 kleine Positionsanfragen und eine anschließende Dezimalakkumulation.
Die C++-, Python- und Java-Implementierungen speichern die beiden Startstrings und erzeugen die Folge \(L_k\) iterativ. Für jede Anfrage wird die Tabelle so weit verlängert, bis der letzte Eintrag mindestens so groß ist wie die angefragte Position. Weil bereits \(F_{74}\) die größte Position abdeckt, bleibt diese Tabelle sehr klein.
Sobald das passende \(k\) feststeht, läuft die Implementierung in einer Schleife, solange \(k>2\) ist. In jedem Schritt wird die aktuelle Position mit \(L_{k-2}\) verglichen. Im linken Block springt man zu \(F_{k-2}\) und behält die lokale Position bei; im rechten Block zieht man \(L_{k-2}\) ab und springt zu \(F_{k-1}\). Wenn schließlich \(F_1\) oder \(F_2\) erreicht ist, liest der Code die gesuchte Ziffer direkt aus \(A\) bzw. \(B\) aus.
Die einzige Indexfeinheit besteht darin, dass die Mathematik 1-indiziert formuliert ist, Programmiersprachen-Strings aber 0-indiziert adressiert werden. Der letzte Zugriff verwendet daher die Position \(t-1\) im gewählten Startstring.
Nach jeder Ziffernabfrage addiert die Implementierung den Wert mit Gewicht \(10^n\) zur laufenden Summe. Alle drei Sprachversionen benutzen dieselben achtzehn Positionen und dieselbe Abstiegslogik; nur der numerische Datentyp für den Akkumulator ist sprachabhängig.
Sei \(k(t)\) der kleinste Index mit \(L_{k(t)}\ge t\). Dann benötigt eine einzelne Anfrage genau einen Abstiegsentscheid pro Ebene, bis ein Startstring erreicht ist. Die Laufzeit ist also \(O(k(t))\). Weil \(L_k=100f_k\) gilt und Fibonacci-Zahlen wie \(\Theta(\varphi^k)\) wachsen, ist das gleichbedeutend mit \(O(\log t)\).
Für Problem 230 gibt es nur 18 Anfragen, und selbst die größte beginnt bei \(k=74\). Insgesamt sind also nur wenige hundert einfache Ganzzahloperationen nötig. Der Speicherverbrauch ist \(O(k_{\max})\) für die Längentabelle, hier also nur einige Dutzend 64-Bit-Werte.
İki sabit 100 basamaklı dize \(A\) ve \(B\) ile başlıyoruz. Bunlardan Fibonacci kelimeleri
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3)$$
şeklinde tanımlanıyor; yan yana yazma işlemi dize birleştirmesidir. Bu kelimeler çok hızlı büyüdüğü için amaç onları açıkça üretmek değil, yalnızca belirli konumlardaki basamakları elde etmektir.
Pozitif bir \(t\) için \(L_k=|F_k|\) olsun ve \(k(t)\), \(L_{k(t)}\ge t\) koşulunu sağlayan en küçük indeks olsun. O zaman \(D_{A,B}(t)\), bu konumu ilk kez kapsayan Fibonacci kelimesinin \(t\). basamağıdır. Sorulan sayı da
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big)$$
ifadesidir. En büyük sorgu konumu \(450\cdot 7^{17}=104683731294243150\) olduğundan, kelimeyi doğrudan kurmaya çalışan her yöntem baştan elenir. Çözüm yalnızca uzunluklar ve indeks dönüşümleriyle çalışır.
Ana fikir şudur: bir birleşik kelimenin içindeki bir konum, daha küçük bir kelimedeki tek bir konuma geri indirilebilir. Bu indirgeme tekrarlandığında, devasa dize problemi kısa bir Fibonacci uzunluk tablosu üzerinde yürüyen bir sürece dönüşür.
\(L_k=|F_k|\) dersek, birleştirme işleminden hemen
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3)$$
elde edilir. Yani uzunluklar da Fibonacci sayılarıyla aynı bağıntıyı izler. \(f_1=f_2=1\) ve \(f_k=f_{k-2}+f_{k-1}\) olmak üzere
$$L_k=100f_k$$
yazabiliriz. Bu çok önemlidir; çünkü algoritma kelimelerin kendisini hiç tutmaz, yalnızca hedef konumun sol blokta mı sağ blokta mı olduğunu anlamaya yetecek kadar uzunluk değeri üretir. Fibonacci büyümesi üstel olduğu için en büyük sorgu bile \(F_{74}\) ile kapsanır; dolayısıyla birkaç düzine uzunluk yeterlidir.
\(k\ge 3\) iken \(F_k\) içindeki \(t\). basamağı aradığımızı düşünelim. Çünkü
$$F_k=F_{k-2}F_{k-1},$$
\(F_k\)'nin ilk \(L_{k-2}\) konumu \(F_{k-2}\)'den, kalan \(L_{k-1}\) konumu ise \(F_{k-1}\)'den gelir. Bu yüzden
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
Problemin özündeki formül budur. \(L_{k-2}\) ile yapılan tek bir karşılaştırma, aranan basamağın sol parçada mı sağ parçada mı olduğunu söyler; sağ parçada ise yerel indeks, sol parçanın tamamı çıkarılarak bulunur.
Başlangıçta \(k=k(t)\) alınır; yani \(L_k\ge t\) koşulunu sağlayan en küçük indeks. Her adımda \((k,t)\) durumu şu anlama gelir: “Aranan cevap, \(F_k\)'nin \(t\). basamağıdır.” Geri iniş kuralı bu anlamı aynen korurken \(k\)'yi küçültür.
Konum sol bloktaysa \((k,t)\) yerine \((k-2,t)\) geçer. Sağ bloktaysa \((k,t)\) yerine \((k-1,t-L_{k-2})\) geçer. Her iki durumda da kelime indeksi azalır; bu yüzden süreç zorunlu olarak \(F_1\) ya da \(F_2\)'de biter. Orada cevap doğrudan \(A\) veya \(B\) dizisinden okunur.
Yani dallanıp budaklanan bir arama ağacı yoktur. Her sorgu için birleştirme yapısında aşağı doğru giden tek bir geçerli yol vardır.
Problem metnindeki daha kısa başlangıç dizelerini kullanalım:
$$A=1415926535,\qquad B=8979323846.$$
Uzunluklar \(10,10,20,30,50,\dots\) olur. \(35\). konumu ilk kez kapsayan Fibonacci kelimesi \(F_5\)'tir; çünkü \(L_4=30<35\le 50=L_5\).
Şimdi geri iniş kuralını uygulayalım:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
Gerekçe
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10$$
şeklindedir. Sonuçta aranan basamak \(A\)'nın 5. basamağıdır; o da \(9\) eder. Büyük görünen bir indeksin nasıl temel dizelerden birine kadar çöktüğünü bu örnek açıkça gösterir.
Asıl problem için
$$p_n=(127+19n)7^n\qquad (0\le n\le 17)$$
tanımını yapalım. Her \(p_n\) bağımsız olarak işlenir: önce \(D_{A,B}(p_n)\) geri inişle bulunur, sonra bulunan basamak \(10^n\) ağırlığıyla sonuca eklenir. Böylece aranan değer
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17})$$
olur. Yani küresel problem gerçekte 18 küçük konum sorgusunun ve bir ondalık biriktirmenin toplamıdır.
C++, Python ve Java uygulamaları iki başlangıç dizesini saklar ve \(L_k\) dizisini yinelemeli olarak üretir. Her sorgu için tablo, son eleman istenen konumdan büyük ya da ona eşit olana kadar uzatılır. En büyük sorgu bile \(F_{74}\) ile karşılandığı için bu tablo küçüktür.
Uygun \(k\) bulunduktan sonra uygulama \(k>2\) olduğu sürece döngüye girer. Her adımda mevcut konum \(L_{k-2}\) ile karşılaştırılır. Sol blokta kalıyorsa aynı yerel indeksle \(F_{k-2}\)'ye geçilir; sağ blokta kalıyorsa \(L_{k-2}\) çıkarılır ve \(F_{k-1}\)'e geçilir. Döngü sonunda \(F_1\) ya da \(F_2\)'ye gelindiğinde, ilgili basamak \(A\) ya da \(B\) içinden doğrudan okunur.
Tek indeks hassasiyeti şudur: matematik 1-indeksli yazılmıştır, programlama dizesi erişimleri ise 0-indekslidir. Bu nedenle son karakter erişimi seçilen temel dizide \(t-1\) konumunu kullanır.
Her basamak bulunduktan sonra uygulama onu \(10^n\) katsayısıyla çalışan toplam değişkenine ekler. Üç dildeki sürümler aynı 18 sorguyu ve aynı geri iniş mantığını kullanır; yalnızca son biriktiriciyi tutan sayısal tür değişir.
\(k(t)\), \(L_{k(t)}\ge t\) koşulunu sağlayan en küçük indeks olsun. O halde tek bir sorgu, temel dizeye inene kadar seviye başına tam bir karar verir. Bu yüzden çalışma süresi \(O(k(t))\)'dir. \(L_k=100f_k\) ve Fibonacci sayıları \(f_k=\Theta(\varphi^k)\) olduğundan bu, \(O(\log t)\) ile aynıdır.
Problem 230 için yalnızca 18 sorgu vardır ve en büyüğü bile \(k=74\) düzeyinden başlar. Dolayısıyla toplam iş birkaç yüz basit tamsayı işleminden ibarettir. Bellek kullanımı, uzunluk tablosu için \(O(k_{\max})\) olur; burada bu da yalnızca birkaç düzine 64 bitlik değer demektir.
Partimos de dos cadenas fijas de 100 dígitos, \(A\) y \(B\). A partir de ellas se definen las palabras de Fibonacci mediante
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
donde la yuxtaposición significa concatenación. Estas palabras crecen tan deprisa que no se pueden construir explícitamente; lo que interesa son solo ciertos dígitos en posiciones enormes.
Para un entero positivo \(t\), sea \(L_k=|F_k|\), y sea \(k(t)\) el menor índice tal que \(L_{k(t)}\ge t\). Entonces \(D_{A,B}(t)\) es el dígito \(t\)-ésimo de la primera palabra de Fibonacci suficientemente larga para contener esa posición. La cantidad pedida es
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
La mayor posición consultada es \(450\cdot 7^{17}=104683731294243150\), así que cualquier estrategia basada en materializar la palabra completa es inviable. La solución trabaja solo con longitudes y con el traslado del índice de un bloque a otro.
La idea central es que una posición dentro de una concatenación pertenece exactamente a uno de sus dos bloques. Si repetimos esa observación, una consulta gigantesca se reduce a un descenso corto por una tabla de longitudes de tipo Fibonacci.
Si \(L_k=|F_k|\), la concatenación da inmediatamente
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
Por tanto, las longitudes obedecen la misma recurrencia que los números de Fibonacci. Si \(f_1=f_2=1\) y \(f_k=f_{k-2}+f_{k-1}\), entonces
$$L_k=100f_k.$$
Esto es exactamente lo que hace viable el problema: nunca hace falta construir \(F_k\), solo conocer suficientes valores de \(L_k\) para decidir si la posición buscada cae en el bloque izquierdo o en el derecho. Como el crecimiento de Fibonacci es exponencial, incluso la consulta más grande queda cubierta en \(F_{74}\).
Supongamos que queremos el dígito \(t\)-ésimo de \(F_k\) con \(k\ge 3\). Como
$$F_k=F_{k-2}F_{k-1},$$
las primeras \(L_{k-2}\) posiciones de \(F_k\) pertenecen a \(F_{k-2}\), y las siguientes \(L_{k-1}\) posiciones pertenecen a \(F_{k-1}\). Por ello,
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
Esta es la fórmula fundamental. Una sola comparación con \(L_{k-2}\) decide en qué mitad está el dígito buscado, y en la mitad derecha el índice local se obtiene restando toda la longitud del bloque izquierdo.
El proceso empieza en \(k=k(t)\), el menor índice con \(L_k\ge t\). En cada momento, el estado \((k,t)\) significa: “la respuesta es el dígito \(t\)-ésimo de \(F_k\)”. La regla de descenso conserva exactamente esa afirmación, pero reduce el índice de la palabra.
Si la posición está en el bloque izquierdo, sustituimos \((k,t)\) por \((k-2,t)\). Si está en el bloque derecho, sustituimos \((k,t)\) por \((k-1,t-L_{k-2})\). En ambos casos, \(k\) disminuye, así que el proceso termina forzosamente en \(F_1\) o \(F_2\). En ese punto el dígito se lee directamente en la cadena base \(A\) o \(B\).
No se recorre un árbol de posibilidades. Para cada consulta existe un único camino descendente dentro de la estructura de concatenación.
Tomemos las semillas cortas del enunciado,
$$A=1415926535,\qquad B=8979323846.$$
Sus longitudes generan \(10,10,20,30,50,\dots\). La primera palabra suficientemente larga para contener la posición \(35\) es \(F_5\), porque \(L_4=30<35\le 50=L_5\).
Ahora aplicamos la regla de descenso:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
La justificación es
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
Así, el dígito buscado es el 5.º dígito de \(A\), que vale \(9\). Este ejemplo deja claro cómo una posición aparentemente enorme acaba convertida en un acceso directo a una de las dos semillas.
Para el problema real se definen
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
Cada \(p_n\) se procesa de forma independiente: se calcula \(D_{A,B}(p_n)\) mediante el descenso anterior y luego ese dígito se añade con peso decimal \(10^n\). En consecuencia, el valor final es
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
El problema completo queda reducido a 18 extracciones de un solo dígito y una acumulación decimal muy pequeña.
Las implementaciones en C++, Python y Java almacenan las dos cadenas base y generan iterativamente la secuencia \(L_k\). Para cada consulta amplían la tabla hasta que la última longitud sea al menos tan grande como la posición pedida. Como la consulta máxima ya cabe en \(F_{74}\), esta tabla es mínima.
Una vez conocido el \(k\) adecuado, la implementación repite un bucle mientras \(k>2\). En cada iteración compara la posición actual con \(L_{k-2}\). Si la posición cae en el bloque izquierdo, salta a \(F_{k-2}\) sin cambiar el índice local; si cae en el bloque derecho, resta \(L_{k-2}\) y salta a \(F_{k-1}\). Cuando el proceso alcanza \(F_1\) o \(F_2\), el código lee directamente el dígito correspondiente de \(A\) o \(B\).
El único detalle de indexación es que la formulación matemática usa posiciones 1-indexadas, mientras que las cadenas en programación son 0-indexadas. Por eso el acceso final al carácter utiliza la posición \(t-1\) dentro de la semilla elegida.
Después de cada extracción, la implementación añade el dígito a un acumulador con peso \(10^n\). Las tres versiones siguen exactamente las mismas dieciocho consultas y la misma lógica de descenso; solo cambia el tipo numérico utilizado para guardar el resultado final.
Si \(k(t)\) es el menor índice tal que \(L_{k(t)}\ge t\), una consulta individual realiza un paso de descenso por nivel hasta llegar a una semilla. Su coste temporal es, por tanto, \(O(k(t))\). Como \(L_k=100f_k\) y \(f_k=\Theta(\varphi^k)\), esto equivale a \(O(\log t)\).
En el Problema 230 solo hay 18 consultas, y la mayor de ellas empieza en \(k=74\). En total, el trabajo real consiste en unos pocos cientos de operaciones enteras sencillas. El uso de memoria es \(O(k_{\max})\) por la tabla de longitudes, es decir, apenas unas cuantas decenas de valores de 64 bits.
题目给出两个固定的 100 位数字串 \(A\) 与 \(B\)，并据此定义 Fibonacci 字符串
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
其中相邻书写表示字符串拼接。随着 \(k\) 增大，这些字符串会膨胀到天文级长度，因此目标并不是把它们真的构造出来，而是只回答若干个指定位置上的数字。
对任意正整数 \(t\)，记 \(L_k=|F_k|\)，再记 \(k(t)\) 为满足 \(L_{k(t)}\ge t\) 的最小下标。那么 \(D_{A,B}(t)\) 就表示“第一个长度足以覆盖位置 \(t\) 的 Fibonacci 字符串”的第 \(t\) 位数字。题目要求计算
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
最大的查询位置是 \(450\cdot 7^{17}=104683731294243150\)。这意味着任何显式构造字符串的做法都没有现实可能，真正可行的路径只能是研究长度递推与位置映射。
整个解法建立在一个非常具体的事实之上：拼接字符串中的某个位置，必然只属于左半部分或右半部分中的一个。沿着这个判断不断向下追踪，就能把超大位置问题压缩成一条很短的递推路径。
令 \(L_k=|F_k|\)。由于 \(F_k\) 由两个更早的字符串拼接而成，长度立刻满足
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
也就是说，长度序列本身也满足与 Fibonacci 数列相同的递推关系。若记 \(f_1=f_2=1\)，\(f_k=f_{k-2}+f_{k-1}\)，则有
$$L_k=100f_k.$$
这一步决定了算法为什么可行。程序从头到尾都不需要真正保存 \(F_k\) 的内容，只要保存足够多的 \(L_k\)，以便判断目标位置落在当前拼接的左段还是右段。由于 Fibonacci 增长是指数级的，题目中最大的查询位置也只需要走到 \(F_{74}\) 为止。
设我们要找的是 \(F_k\) 的第 \(t\) 位，并且 \(k\ge 3\)。因为
$$F_k=F_{k-2}F_{k-1},$$
所以 \(F_k\) 的前 \(L_{k-2}\) 位全部来自 \(F_{k-2}\)，后面的 \(L_{k-1}\) 位全部来自 \(F_{k-1}\)。于是目标数字满足
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
这就是本题的核心递推。一次与 \(L_{k-2}\) 的比较，就能决定目标位落在左块还是右块；如果在右块中，只需要把左块的总长度减掉，得到它在右块内部的局部位置。
计算从 \(k=k(t)\) 开始，也就是从“第一个足够长的 Fibonacci 字符串”开始。此后每个状态 \((k,t)\) 都保持同一个含义：“答案是 \(F_k\) 的第 \(t\) 位数字。” 上面的下钻规则不会改变这个含义，只会把问题搬到更小的字符串上。
如果目标位置在左块内，就把 \((k,t)\) 变成 \((k-2,t)\)；如果在右块内，就把 \((k,t)\) 变成 \((k-1,t-L_{k-2})\)。无论哪一种，\(k\) 都会严格减小，因此过程必然在有限步后落到 \(k=1\) 或 \(k=2\)。那时答案就不再需要递推，直接读取种子串 \(A\) 或 \(B\) 的对应位置即可。
需要强调的是：这里并没有搜索树，也没有回溯。每次查询只有一条唯一的下降路径。
用题目中的短种子串作示范：
$$A=1415926535,\qquad B=8979323846.$$
对应长度序列是 \(10,10,20,30,50,\dots\)。位置 \(35\) 第一次出现于 \(F_5\) 中，因为 \(L_4=30<35\le 50=L_5\)。
现在按规则下钻：
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
每一步的理由分别是
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
最后问题变成“\(A\) 的第 5 位是什么”，答案显然是 \(9\)。这个例子说明，大下标查询并不需要展开任何长字符串，只要沿着拼接结构不断回退即可。
对真实问题，定义
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
每个 \(p_n\) 都独立处理：先用上面的下钻规则求出 \(D_{A,B}(p_n)\)，再把它作为十进制中的第 \(n\) 位贡献加入总和。因此最终答案就是
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
换句话说，整个题目并不是“处理一个超长字符串”，而只是“做 18 次单点查询，再按十进制权重拼起来”。
C++、Python 和 Java 三个实现都先保存两个 100 位种子串，然后用 \(L_k=L_{k-2}+L_{k-1}\) 逐步生成长度表。对某个查询位置 \(t\)，程序会一直扩展这张表，直到最后一个长度不小于 \(t\)。由于题目中的最大位置在 \(F_{74}\) 处就已经被覆盖，这个表非常短。
找到合适的 \(k\) 之后，实现会在 \(k>2\) 时不断循环。每次循环只做一个判断：当前 \(t\) 是否不超过 \(L_{k-2}\)。如果是，就跳到 \(F_{k-2}\) 而保持位置不变；如果不是，就先减去 \(L_{k-2}\)，再跳到 \(F_{k-1}\)。循环结束时，一定已经落到 \(F_1\) 或 \(F_2\)，于是程序直接读取 \(A\) 或 \(B\) 中对应的字符。
这里唯一需要注意的是索引约定：数学描述采用 1 下标，而程序中的字符串访问通常采用 0 下标，所以最后真正读取字符时用的是位置 \(t-1\)。
程序依次处理 18 个位置 \(p_n=(127+19n)7^n\)。每得到一个数字，就按权重 \(10^n\) 加入累计结果。三个语言版本在算法上完全一致，差别只在于保存最终结果时所使用的整数类型。
若 \(k(t)\) 表示满足 \(L_{k(t)}\ge t\) 的最小下标，那么一次查询恰好沿着长度表向下走若干层，直到抵达 \(F_1\) 或 \(F_2\)。因此单次时间复杂度是 \(O(k(t))\)。由于 \(L_k=100f_k\)，而 Fibonacci 数满足 \(f_k=\Theta(\varphi^k)\)，这又等价于 \(O(\log t)\)。
对本题而言，总共只有 18 次查询，而且最大的查询也不过从 \(k=74\) 开始。所以实际运行量只是一两百步简单的整数比较与减法。空间复杂度为 \(O(k_{\max})\)，对应的只是几十个 64 位长度值。
Даны две фиксированные строки из 100 цифр, \(A\) и \(B\). По ним строятся слова Фибоначчи
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
где соседняя запись означает конкатенацию. Эти слова растут настолько быстро, что строить их явно нельзя; нужно лишь находить отдельные цифры на очень больших позициях.
Для положительного \(t\) положим \(L_k=|F_k|\), а через \(k(t)\) обозначим наименьший индекс, для которого \(L_{k(t)}\ge t\). Тогда \(D_{A,B}(t)\) есть \(t\)-я цифра первого слова Фибоначчи, в котором позиция \(t\) уже существует. Требуется вычислить
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
Максимальная запрашиваемая позиция равна \(450\cdot 7^{17}=104683731294243150\), поэтому любые попытки материализовать строку обречены. Рабочее решение опирается только на длины и на перенос позиции внутрь меньшего блока.
Основная идея очень конкретна: каждая позиция внутри конкатенации принадлежит либо левому куску, либо правому. Если повторять это наблюдение, гигантский запрос по строке сводится к короткому спуску по таблице длин, удовлетворяющих рекурсии Фибоначчи.
Обозначим \(L_k=|F_k|\). Из определения через конкатенацию сразу следует
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
Значит, длины удовлетворяют той же рекурсии, что и числа Фибоначчи. Если \(f_1=f_2=1\) и \(f_k=f_{k-2}+f_{k-1}\), то
$$L_k=100f_k.$$
Это и делает задачу посильной: сами слова хранить не нужно, достаточно знать столько значений \(L_k\), сколько нужно для определения, попадает ли позиция в левую или правую часть текущего слова. Благодаря экспоненциальному росту уже \(F_{74}\) покрывает максимальный запрос.
Пусть требуется найти \(t\)-ю цифру слова \(F_k\) при \(k\ge 3\). Так как
$$F_k=F_{k-2}F_{k-1},$$
первые \(L_{k-2}\) позиций принадлежат \(F_{k-2}\), а следующие \(L_{k-1}\) позиций принадлежат \(F_{k-1}\). Поэтому
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
Это и есть центральная формула задачи. Одно сравнение с \(L_{k-2}\) говорит, в какой половине находится искомая цифра; если в правой, то локальная позиция получается вычитанием длины всего левого блока.
Стартуем с \(k=k(t)\), то есть с наименьшего индекса, для которого \(L_k\ge t\). На каждом шаге состояние \((k,t)\) означает: «ответом является \(t\)-я цифра слова \(F_k\)». Приведенное выше правило сохраняет этот смысл, но уменьшает индекс слова.
Если позиция лежит в левом блоке, состояние меняется на \((k-2,t)\). Если она лежит в правом блоке, состояние меняется на \((k-1,t-L_{k-2})\). В обоих случаях \(k\) строго уменьшается, поэтому через конечное число шагов процесс приходит к \(F_1\) или \(F_2\). Там цифра уже считывается напрямую из строки \(A\) или \(B\).
Никакого дерева вариантов здесь нет. Для каждого запроса существует ровно один корректный путь вниз по структуре конкатенаций.
Возьмем короткие начальные строки из условия:
$$A=1415926535,\qquad B=8979323846.$$
Тогда длины равны \(10,10,20,30,50,\dots\). Первая строка, содержащая позицию \(35\), это \(F_5\), потому что \(L_4=30<35\le 50=L_5\).
Теперь применим правило спуска:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
Пояснение такое:
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
Следовательно, искомая цифра совпадает с 5-й цифрой строки \(A\), то есть равна \(9\). Этот пример наглядно показывает, как большая позиция последовательно схлопывается до прямого обращения к базовой строке.
Для настоящей задачи вводятся позиции
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
Каждая позиция \(p_n\) обрабатывается независимо: сначала по правилу спуска находится \(D_{A,B}(p_n)\), затем эта цифра добавляется к ответу с десятичным весом \(10^n\). Итак, искомое число имеет вид
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
То есть вся задача сводится к 18 точечным запросам и очень небольшой десятичной сборке результата.
Реализации на C++, Python и Java хранят две базовые строки и итеративно строят последовательность \(L_k\). Для каждого запроса таблица продлевается до тех пор, пока последний элемент не станет не меньше нужной позиции. Поскольку максимальная позиция уже покрывается словом \(F_{74}\), эта таблица остается очень короткой.
После выбора подходящего \(k\) реализация выполняет цикл, пока \(k>2\). На каждой итерации она сравнивает текущую позицию с \(L_{k-2}\). Если позиция попадает в левый блок, переход выполняется к \(F_{k-2}\) без изменения локального индекса; если в правый, сначала вычитается \(L_{k-2}\), а затем происходит переход к \(F_{k-1}\). Когда процесс достигает \(F_1\) или \(F_2\), код берет нужную цифру напрямую из \(A\) или \(B\).
Единственный технический нюанс связан с индексацией: математическая формулировка использует нумерацию с 1, а строки в программах индексируются с 0. Поэтому при финальном чтении символа используется позиция \(t-1\).
После извлечения каждой цифры реализация добавляет ее к накопителю с весом \(10^n\). Все три языковые версии используют один и тот же набор из 18 запросов и одну и ту же логику спуска; различается только тип числа, в котором хранится итоговый результат.
Пусть \(k(t)\) есть минимальный индекс, для которого \(L_{k(t)}\ge t\). Тогда один запрос делает по одному шагу спуска на каждом уровне, пока не дойдет до базовой строки. Время работы составляет \(O(k(t))\). Поскольку \(L_k=100f_k\), а числа Фибоначчи растут как \(f_k=\Theta(\varphi^k)\), это то же самое, что \(O(\log t)\).
В задаче 230 всего 18 запросов, и даже самый большой начинается с уровня \(k=74\). Следовательно, фактический объем вычислений составляет всего несколько сотен простых операций сравнения и вычитания. Память имеет порядок \(O(k_{\max})\) для таблицы длин, то есть это лишь несколько десятков 64-битных значений.
نبدأ بسلسلتين ثابتتين من 100 رقم هما \(A\) و\(B\). ومنهما تُعرَّف كلمات فيبوناتشي على الصورة
$$F_1=A,\qquad F_2=B,\qquad F_k=F_{k-2}F_{k-1}\quad (k\ge 3),$$
حيث يعني وضع السلسلتين متجاورتين عملية الدمج النصي. هذه الكلمات تنمو بسرعة هائلة جدًا، لذلك لا يمكن بناؤها حرفيًا، والمطلوب في الحقيقة هو استخراج أرقام مفردة من مواضع ضخمة جدًا داخلها.
لكل عدد موجب \(t\)، لنكتب \(L_k=|F_k|\)، ولنعرّف \(k(t)\) بأنه أصغر فهرس يحقق \(L_{k(t)}\ge t\). عندئذٍ يكون \(D_{A,B}(t)\) هو الرقم الواقع في الموضع \(t\) من أول كلمة فيبوناتشي طولها يكفي لاحتواء هذا الموضع. والكمية المطلوبة في المسألة هي
$$\sum_{n=0}^{17} 10^n\,D_{A,B}\!\big((127+19n)7^n\big).$$
أكبر موضع مطلوب هو \(450\cdot 7^{17}=104683731294243150\)، ولهذا فإن أي محاولة لبناء الكلمة نفسها غير عملية تمامًا. الحل الحقيقي يعتمد فقط على أطوال الكلمات وعلى تحويل الموضع إلى موضع مكافئ داخل جزء أصغر.
فكرة الحل شديدة التحديد: أي موضع داخل كلمة ناتجة عن دمج سلسلتين لا بد أن يكون واقعًا إما في الجزء الأيسر وإما في الجزء الأيمن. بتكرار هذا الحكم البسيط، يتحول استعلام هائل الحجم إلى سلسلة قصيرة من الخطوات فوق جدول أطوال فيبوناتشي.
إذا كتبنا \(L_k=|F_k|\)، فإن الدمج النصي يعطي مباشرة
$$L_1=L_2=100,\qquad L_k=L_{k-2}+L_{k-1}\quad (k\ge 3).$$
إذن أطوال الكلمات تتبع علاقة فيبوناتشي نفسها. وإذا عرّفنا \(f_1=f_2=1\) و\(f_k=f_{k-2}+f_{k-1}\)، فإن
$$L_k=100f_k.$$
هذه الملاحظة هي سبب إمكانية الحل أصلًا. فالخوارزمية لا تحتاج إلى تخزين \(F_k\) نفسها، بل يكفيها تخزين عدد صغير من قيم \(L_k\) لمعرفة هل الموضع المطلوب يقع في الجزء الأيسر أم الأيمن. وبما أن نمو فيبوناتشي أسي، فإن أكبر موضع في هذه المسألة يُغطَّى بالفعل عند \(F_{74}\).
لنفترض أننا نريد الرقم في الموضع \(t\) من \(F_k\) مع \(k\ge 3\). بما أن
$$F_k=F_{k-2}F_{k-1},$$
فإن أول \(L_{k-2}\) موضعًا من \(F_k\) يأتي من \(F_{k-2}\)، بينما تأتي المواضع الباقية من \(F_{k-1}\). لذلك يتحقق
$$\operatorname{digit}(k,t)= \begin{cases} \operatorname{digit}(k-2,t), & 1\le t\le L_{k-2},\\[4pt] \operatorname{digit}(k-1,t-L_{k-2}), & L_{k-2}<t\le L_k. \end{cases}$$
هذه هي الصيغة الجوهرية في المسألة. مقارنة واحدة مع \(L_{k-2}\) تكفي لتحديد هل الرقم المطلوب موجود في النصف الأيسر أو الأيمن، وإذا كان في النصف الأيمن فنطرح طول الجزء الأيسر كله لنحصل على الفهرس المحلي داخل الجزء الأيمن.
نبدأ من \(k=k(t)\)، أي من أصغر كلمة طولها يكفي لاحتواء الموضع المطلوب. وعند كل خطوة يكون معنى الحالة \((k,t)\) هو: "الجواب هو الرقم في الموضع \(t\) من \(F_k\)". قاعدة الهبوط السابقة تحافظ على هذا المعنى تمامًا، لكنها تجعل فهرس الكلمة أصغر.
إذا كان الموضع في الجزء الأيسر، نستبدل \((k,t)\) بـ \((k-2,t)\). وإذا كان في الجزء الأيمن، نستبدل \((k,t)\) بـ \((k-1,t-L_{k-2})\). وفي الحالتين ينخفض \(k\) نزولًا صارمًا، ولذلك لا بد أن تنتهي العملية بعد عدد محدود من الخطوات عند \(F_1\) أو \(F_2\). وهناك يصبح الجواب مجرد قراءة مباشرة من السلسلة \(A\) أو \(B\).
المهم هنا أنه لا توجد شجرة بحث ولا تفرعات كثيرة؛ لكل استعلام مسار هبوط وحيد داخل بنية الدمج.
لنستخدم السلسلتين القصيرتين الواردتين في نص المسألة:
$$A=1415926535,\qquad B=8979323846.$$
عندها تكون الأطوال \(10,10,20,30,50,\dots\). وأول كلمة تحتوي الموضع \(35\) هي \(F_5\)، لأن \(L_4=30<35\le 50=L_5\).
نطبق الآن قاعدة الهبوط:
$$ (5,35)\to(4,15)\to(3,5)\to(1,5). $$
والسبب هو
$$35>L_3=20,\qquad 15>L_2=10,\qquad 5\le L_1=10.$$
إذن الرقم المطلوب هو الرقم الخامس من \(A\)، وهو \(9\). هذا المثال يوضح كيف ينهار موضع كبير ظاهريًا إلى وصول مباشر داخل إحدى السلسلتين الأساسيتين.
في المسألة الفعلية نعرّف
$$p_n=(127+19n)7^n\qquad (0\le n\le 17).$$
كل قيمة \(p_n\) تُعالَج وحدها: نحسب أولًا \(D_{A,B}(p_n)\) بواسطة الهبوط السابق، ثم نضيف الرقم الناتج بوزن عشري \(10^n\). ومن ثم يكون الجواب النهائي
$$D_{A,B}(p_0)+10D_{A,B}(p_1)+10^2D_{A,B}(p_2)+\cdots+10^{17}D_{A,B}(p_{17}).$$
بذلك يتبين أن المسألة كلها ليست أكثر من 18 عملية استخراج لرقم واحد، يتبعها تجميع عشري بسيط.
تبدأ تطبيقات C++ وPython وJava بحفظ السلسلتين الأساسيتين، ثم توليد جدول الأطوال \(L_k\) على نحو تكراري. ولكل استعلام تتابع الشيفرة توسيع هذا الجدول حتى يصبح آخر طول فيه أكبر من الموضع المطلوب أو مساويًا له. وبما أن أكبر استعلام لا يحتاج إلى ما بعد \(F_{74}\)، فإن هذا الجدول يبقى صغيرًا جدًا.
بعد معرفة \(k\) المناسب، تدخل الشيفرة في حلقة ما دام \(k>2\). في كل دورة تُقارَن القيمة الحالية \(t\) مع \(L_{k-2}\). إذا كانت داخل الجزء الأيسر، تنتقل الشيفرة إلى \(F_{k-2}\) دون تغيير الفهرس المحلي. وإذا كانت داخل الجزء الأيمن، تطرح \(L_{k-2}\) ثم تنتقل إلى \(F_{k-1}\). وعندما تصل العملية إلى \(F_1\) أو \(F_2\)، يُقرأ الرقم مباشرة من \(A\) أو \(B\).
التفصيلة الوحيدة المتعلقة بالفهرسة هي أن الصياغة الرياضية تستعمل ترقيمًا يبدأ من 1، بينما السلاسل في البرمجة تُفهرَس عادة من 0. لذلك فإن الوصول النهائي إلى المحرف يستخدم الموضع \(t-1\).
بعد استخراج كل رقم، تضيفه الشيفرة إلى مجموع جارٍ بوزن \(10^n\). النسخ الثلاث في اللغات المختلفة تطبق المنطق نفسه تمامًا على الاستعلامات الثمانية عشر نفسها؛ والاختلاف الوحيد بينها هو نوع العدد المستخدم لحفظ الناتج النهائي.
إذا كان \(k(t)\) هو أصغر فهرس يحقق \(L_{k(t)}\ge t\)، فإن الاستعلام الواحد ينفذ خطوة هبوط واحدة في كل مستوى حتى يصل إلى سلسلة أساسية. لذلك يكون الزمن \(O(k(t))\). وبما أن \(L_k=100f_k\) وأن أعداد فيبوناتشي تحقق \(f_k=\Theta(\varphi^k)\)، فهذا يكافئ \(O(\log t)\).
في هذه المسألة لا يوجد سوى 18 استعلامًا، وحتى أكبرها يبدأ من \(k=74\) فقط. لذا فإجمالي العمل الحقيقي لا يتجاوز بضع مئات من عمليات المقارنة والطرح على أعداد صحيحة. أما الذاكرة فهي \(O(k_{\max})\) لجدول الأطوال، أي بضع عشرات من القيم فقط.