At each step we sample one symbol from \(\{I,V,X,L,C,D,M,\#\}\). Each Roman letter has probability \(0.14\), while \(\#\) has probability \(0.02\). A sampled letter is appended only if the new string is still a valid minimal Roman numeral; otherwise that letter is ignored and the current string stays unchanged. The process ends at the first \(\#\), and the empty string counts as value \(0\).
The task is to compute the expected final value, rounded to eight decimal places. The difficulty is that the random stream is infinite in principle, but the validity rule collapses the process to a small structured set of states.
The C++, Python, and Java implementations model the process as a finite expectation system for the non-thousands part, plus one extra equation for the unbounded prefix of \(M\)'s.
For each integer \(r\in\{1,2,\dots,999\}\), let \(s(r)\) be its unique minimal Roman numeral. These \(999\) strings form the finite state space for all numerals that do not begin with a leading run of thousands.
For a letter \(\ell\in\{I,V,X,L,C,D,M\}\), append \(\ell\) to the current minimal numeral \(s(r)\). If the result is itself the minimal Roman numeral of some integer \(v\) with \(1\le v\le 999\), then we move to state \(v\). Otherwise the letter is rejected and we remain at \(r\).
This turns the Roman numeral rule into a deterministic transition map \(T(r,\ell)\) on a fixed set of states.
If a letter is accepted, it extends the current minimal Roman numeral to a longer valid minimal numeral. That can only increase the represented number, so every accepted transition satisfies
$$T(r,\ell)>r.$$
Therefore the directed graph of accepted transitions on \(\{1,\dots,999\}\) is acyclic when states are ordered by value. This is why the expectation system can be solved by backward substitution from \(999\) down to \(1\).
Rejected letters are different: they do not create new states, they create self-loops.
Let \(E_r\) be the expected final value when the current string already equals the minimal Roman numeral for \(r\). On the very next draw, either \(\#\) appears and we stop with value \(r\), or one of the seven letters is sampled.
So for \(1\le r\le 999\),
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
If exactly \(q_r\) letters are rejected at state \(r\), then those \(q_r\) terms equal \(E_r\) itself. Moving them to the left gives
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
This is the key linear relation used by the implementation.
Minimal Roman numerals are not globally finite, because any number of leading \(M\)'s is allowed. Instead of creating infinitely many states \(1000,2000,3000,\dots\), we isolate that part.
Let \(E_0\) be the expected final value from the empty string. If the first accepted letter is \(M\), we gain \(1000\) immediately and are again in the same “prefix of only \(M\)'s” situation. If the first accepted non-\(M\) letter is one of \(I,V,X,L,C,D\), then we enter one of the finite states \(1,5,10,50,100,500\).
Conditioning on the first draw gives
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
Rearranging,
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
The coefficient \(0.86\) is the probability that the next symbol is not \(M\), and the term \(140\) is the one-step expected contribution \(0.14\times1000\).
Take the current numeral \(X\), which represents \(10\). Appending \(I,V,X,L,C\) gives the valid minimal numerals \(XI,XV,XX,XL,XC\), so these moves go to \(11,15,20,40,90\).
Appending \(D\) or \(M\) does not yield a valid minimal continuation, so those letters are rejected. Thus \(q_{10}=2\), and the state equation becomes
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
Equivalently,
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
This small example shows the two recurring ingredients of the full solution: accepted forward moves and rejected self-loops.
Because every accepted move from \(r\) goes to a larger state, \(E_{999}\) depends only on itself, \(E_{998}\) depends only on itself and already computed larger states, and so on. Therefore we can compute
$$E_{999},E_{998},\dots,E_1$$
in that order without any iterative numerical method. Once these \(999\) values are known, the empty-state equation yields the final expectation immediately.
The C++, Python, and Java implementations first generate the minimal Roman numeral for every integer from \(0\) to \(999\) using the standard greedy token system \(1000,900,500,400,\dots,1\). They then test every state \(r\in\{1,\dots,999\}\) against each of the seven letters by appending that letter, evaluating the candidate numeral numerically, and accepting the transition exactly when the candidate string matches the minimal Roman numeral of its value and stays within \(1\) to \(999\).
After the transition table is built, the implementation processes states from \(999\) downward. For each state it counts rejected letters, sums the expectations of accepted successor states, and solves the rearranged one-line equation for \(E_r\). Finally it substitutes the six entry states \(1,5,10,50,100,500\) into the separate equation for \(E_0\) and prints the result rounded to eight decimal places.
The finite part of the state space has exactly \(999\) states and each state checks exactly \(7\) letters. Building the transitions therefore costs \(O(999\cdot7)\), and solving the expectations costs another \(O(999\cdot7)\). Memory usage is also \(O(999\cdot7)\) if the full transition table is stored, or \(O(999)\) for the expectation array itself. Since \(999\) and \(7\) are fixed constants, the practical complexity is constant time and constant memory.
In jedem Schritt wird ein Symbol aus \(\{I,V,X,L,C,D,M,\#\}\) gezogen. Jeder römische Buchstabe hat Wahrscheinlichkeit \(0{,}14\), das Stoppsymbol \(\#\) hat Wahrscheinlichkeit \(0{,}02\). Ein gezogener Buchstabe wird nur dann angehängt, wenn die neue Zeichenkette weiterhin eine gültige minimale römische Zahl ist; andernfalls wird er verworfen und der aktuelle Zustand bleibt unverändert. Beim ersten \(\#\) endet der Prozess, und die leere Zeichenkette zählt als \(0\).
Gesucht ist der Erwartungswert des Endergebnisses, gerundet auf acht Nachkommastellen. Der Zufallsprozess wirkt zunächst unendlich, lässt sich aber durch die Minimalitätsregel auf eine kleine Zustandsstruktur reduzieren.
Die Implementierungen in C++, Python und Java behandeln das Problem als Erwartungssystem auf endlich vielen Zuständen für den Teil unterhalb von \(1000\) plus einer zusätzlichen Gleichung für den unbegrenzten Präfix aus \(M\)-Zeichen.
Für jedes \(r\in\{1,2,\dots,999\}\) bezeichne \(s(r)\) die eindeutige minimale römische Darstellung von \(r\). Diese \(999\) Zeichenketten bilden den endlichen Zustandsraum für alle Zahlen ohne führenden Tausenderblock.
Für einen Buchstaben \(\ell\in\{I,V,X,L,C,D,M\}\) wird \(\ell\) an \(s(r)\) angehängt. Falls die neue Zeichenkette selbst die minimale römische Darstellung eines Wertes \(v\) mit \(1\le v\le 999\) ist, wechselt der Prozess in Zustand \(v\). Andernfalls wird der Buchstabe abgelehnt und man bleibt in \(r\).
So entsteht eine deterministische Übergangsfunktion \(T(r,\ell)\) auf einer festen endlichen Menge von Zuständen.
Wird ein Buchstabe akzeptiert, so erweitert er die bisherige minimale römische Zahl zu einer längeren gültigen minimalen Zahl. Dadurch wächst der dargestellte Wert stets, also gilt für jeden akzeptierten Übergang
$$T(r,\ell)>r.$$
Damit ist der gerichtete Graph aller akzeptierten Übergänge auf \(\{1,\dots,999\}\) azyklisch, wenn man nach dem Zahlenwert ordnet. Genau deshalb kann das Erwartungssystem rückwärts von \(999\) nach \(1\) gelöst werden.
Abgelehnte Buchstaben erzeugen keine neuen Zustände, sondern Selbstschleifen.
Sei \(E_r\) der Erwartungswert des Endergebnisses, wenn die aktuelle Zeichenkette bereits die minimale römische Darstellung von \(r\) ist. Beim nächsten Zug erscheint entweder \(\#\) und der Prozess endet mit Wert \(r\), oder einer der sieben Buchstaben wird gezogen.
Für \(1\le r\le 999\) gilt daher
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
Wenn in Zustand \(r\) genau \(q_r\) Buchstaben abgelehnt werden, dann sind genau \(q_r\) Summanden gleich \(E_r\). Nach dem Umstellen erhält man
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
Dies ist die zentrale lineare Relation der Lösung.
Minimale römische Zahlen sind nach oben nicht begrenzt, weil beliebig viele führende \(M\)'s erlaubt sind. Statt unendlich viele Zustände \(1000,2000,3000,\dots\) einzuführen, wird dieser Teil isoliert.
Sei \(E_0\) der Erwartungswert beim Start mit leerer Zeichenkette. Falls der erste akzeptierte Buchstabe ein \(M\) ist, gewinnen wir sofort \(1000\) und befinden uns wieder in genau derselben Situation eines reinen \(M\)-Präfixes. Falls der erste akzeptierte Nicht-\(M\)-Buchstabe einer aus \(I,V,X,L,C,D\) ist, gelangen wir in die endlichen Zustände \(1,5,10,50,100,500\).
Durch Fallunterscheidung nach dem ersten Zug folgt
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
Nach Umformen ergibt sich
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
Der Faktor \(0.86\) ist die Wahrscheinlichkeit, dass das nächste Symbol nicht \(M\) ist, und \(140\) ist der Ein-Schritt-Beitrag \(0.14\times1000\).
Betrachte das aktuelle Numeral \(X\), also den Wert \(10\). Die Anhänge \(I,V,X,L,C\) liefern die gültigen minimalen Zahlen \(XI,XV,XX,XL,XC\), also die Zielzustände \(11,15,20,40,90\).
Die Anhänge \(D\) und \(M\) sind keine gültigen minimalen Fortsetzungen und werden deshalb verworfen. Also ist \(q_{10}=2\), und die Zustandsgleichung lautet
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
Äquivalent dazu:
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
Dieses Beispiel zeigt bereits die beiden Bausteine der Gesamtlösung: echte Vorwärtsübergänge und Selbstschleifen durch Ablehnung.
Da jeder akzeptierte Übergang von \(r\) zu einem größeren Zustand führt, hängt \(E_{999}\) nur von sich selbst ab, \(E_{998}\) nur von sich selbst und bereits bekannten größeren Zuständen usw. Man kann also
$$E_{999},E_{998},\dots,E_1$$
direkt in dieser Reihenfolge berechnen, ganz ohne Iterationsverfahren. Sobald diese \(999\) Werte vorliegen, liefert die Gleichung für \(E_0\) sofort die gesuchte Erwartung.
Die Implementierungen in C++, Python und Java erzeugen zunächst für jede Zahl von \(0\) bis \(999\) ihre minimale römische Darstellung mittels des üblichen gierigen Tokensystems \(1000,900,500,400,\dots,1\). Danach prüfen sie für jeden Zustand \(r\in\{1,\dots,999\}\) und jeden der sieben Buchstaben die angehängte Kandidatenzeichenkette, berechnen ihren numerischen Wert und akzeptieren den Übergang genau dann, wenn diese Kandidatenkette mit der minimalen römischen Darstellung dieses Wertes übereinstimmt und im Bereich \(1\) bis \(999\) bleibt.
Anschließend werden die Zustände von \(999\) nach unten verarbeitet. Für jeden Zustand zählt die Implementierung die abgelehnten Buchstaben, summiert die Erwartungswerte aller akzeptierten Nachfolger und löst daraus die umgestellte lineare Gleichung für \(E_r\). Am Ende werden die sechs Einstiegszustände \(1,5,10,50,100,500\) in die separate Gleichung für \(E_0\) eingesetzt und das Ergebnis auf acht Nachkommastellen ausgegeben.
Der endliche Zustandsraum besitzt genau \(999\) Zustände, und in jedem Zustand werden genau \(7\) Buchstaben getestet. Der Aufbau der Übergänge kostet also \(O(999\cdot7)\), und das Lösen der Erwartungswerte nochmals \(O(999\cdot7)\). Der Speicherbedarf liegt bei \(O(999\cdot7)\), wenn alle Übergänge gespeichert werden, beziehungsweise bei \(O(999)\) für das Erwartungsarray selbst. Da \(999\) und \(7\) feste Konstanten sind, ist die praktische Laufzeit konstant und der Speicherverbrauch ebenfalls konstant.
Her adımda \(\{I,V,X,L,C,D,M,\#\}\) kümesinden bir sembol seçilir. Her Roma harfinin olasılığı \(0.14\), durdurma sembolü \(\#\)'in olasılığı \(0.02\)'dir. Seçilen bir harf ancak oluşan yeni dize hâlâ minimal bir Roma rakamıysa eklenir; aksi halde harf reddedilir ve mevcut dize değişmez. İlk \(\#\) geldiğinde süreç durur, boş dize ise \(0\) değerini temsil eder.
İstenen şey son değerin beklenen değeridir ve cevap sekiz ondalık basamağa yuvarlanır. Süreç sonsuz gibi görünse de minimal yazım kuralı onu küçük ve düzenli bir durum uzayına indirger.
C++, Python ve Java implementasyonları, \(1000\)'in altındaki kısım için sonlu bir beklenti sistemi kurar ve sınırsız baştaki \(M\) dizisini ayrı bir denklemle ele alır.
Her \(r\in\{1,2,\dots,999\}\) için \(s(r)\), \(r\)'nin tekil minimal Roma yazımı olsun. Bu \(999\) dize, binlik ön ek başlamadan önceki tüm durumları oluşturur.
\(\ell\in\{I,V,X,L,C,D,M\}\) harflerinden biri için \(\ell\) harfini mevcut minimal yazım \(s(r)\)'nin sonuna ekleriz. Eğer elde edilen yeni dize, \(1\le v\le 999\) aralığında bir \(v\) sayısının yine minimal Roma yazımıysa, yeni durum \(v\) olur. Aksi halde harf reddedilir ve durum \(r\)'de kalır.
Böylece Roman numeral kuralı sabit bir durum kümesi üzerinde tanımlı deterministik bir geçiş fonksiyonu \(T(r,\ell)\) üretir.
Bir harf kabul edildiğinde, mevcut minimal Roma rakamı daha uzun bir geçerli minimal yazıma dönüşür. Bu da temsil edilen sayının arttığı anlamına gelir. Dolayısıyla her kabul edilen geçiş için
$$T(r,\ell)>r$$
olur. Sonuç olarak \(\{1,\dots,999\}\) üzerindeki kabul edilmiş geçişler grafiği, durumlar sayısal sırada dizildiğinde çevrimsizdir. Bu nedenle beklenti denklemleri \(999\)'dan \(1\)'e doğru geri yerine koyma ile çözülebilir.
Reddedilen harfler ise yeni bir durum oluşturmaz; öz-döngü üretir.
\(E_r\), mevcut dize zaten \(r\) sayısının minimal Roma yazımıyken son değerin beklenen değeri olsun. Bir sonraki çekilişte ya \(\#\) gelir ve süreç \(r\) değeriyle biter ya da yedi harften biri seçilir.
Bu yüzden \(1\le r\le 999\) için
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
Eğer \(r\) durumunda tam \(q_r\) tane harf reddediliyorsa, bu \(q_r\) teriminin her biri aslında \(E_r\)'dir. Sol tarafa toplarsak
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
Çözümün temel doğrusal bağıntısı budur.
Minimal Roma yazımları üstten sınırlı değildir; çünkü başta istenildiği kadar \(M\) bulunabilir. Bu yüzden \(1000,2000,3000,\dots\) gibi sonsuz sayıda durum oluşturmak yerine bu kısmı ayrı bir skaler denkleme indirgeriz.
\(E_0\), boş dizeden başlayan beklenen değer olsun. Eğer ilk kabul edilen harf \(M\) ise hemen \(1000\) eklenir ve yine yalnızca \(M\)'lerden oluşan aynı ön ek durumuna dönmüş oluruz. Eğer ilk kabul edilen \(M\) dışı harf \(I,V,X,L,C,D\) harflerinden biriyse, sonlu durumlar olan \(1,5,10,50,100,500\)'e gireriz.
İlk adıma göre koşullandırınca
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
Düzenlersek
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
Buradaki \(0.86\), sıradaki sembolün \(M\) olmama olasılığıdır; \(140\) ise tek adımlık beklenen katkı \(0.14\times1000\)'dir.
Mevcut yazım \(X\), yani değer \(10\) olsun. Sonuna \(I,V,X,L,C\) eklenirse geçerli minimal yazımlar olan \(XI,XV,XX,XL,XC\) elde edilir; bunlar da sırasıyla \(11,15,20,40,90\) durumlarına gider.
\(D\) ve \(M\) eklemeleri minimal geçerli devam üretmez, dolayısıyla reddedilir. Bu yüzden \(q_{10}=2\) ve denklem
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right)$$
olur. Eşdeğer biçimde
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
Bu küçük örnek, bütün çözüm boyunca tekrar eden iki unsuru açıkça gösterir: ileriye giden kabul edilmiş geçişler ve reddedilen harflerden gelen öz-döngüler.
Her kabul edilmiş geçiş \(r\)'den daha büyük bir duruma gittiği için \(E_{999}\) yalnızca kendisine, \(E_{998}\) ise kendisine ve daha önce hesaplanmış daha büyük durumlara bağlıdır. Bu yüzden
$$E_{999},E_{998},\dots,E_1$$
değerleri bu sırayla doğrudan hesaplanabilir; yinelemeli sayısal yöntem gerekmez. Son olarak bu \(999\) değer boş durum denklemiyle birleştirilir ve nihai beklenti bulunur.
C++, Python ve Java implementasyonları önce \(0\) ile \(999\) arasındaki her sayı için standart açgözlü belirteç sistemi \(1000,900,500,400,\dots,1\) kullanılarak minimal Roma yazımını üretir. Sonra her \(r\in\{1,\dots,999\}\) durumu ve her yedi harf için aday diziyi oluşturur, adayın sayısal değerini hesaplar ve ancak aday dize bu değerin minimal Roma yazımıyla tam olarak aynıysa ve değer \(1\) ile \(999\) arasında kalıyorsa geçişi kabul eder.
Geçiş tablosu kurulduktan sonra implementasyon durumları \(999\)'dan aşağı doğru işler. Her durumda reddedilen harf sayısını bulur, kabul edilen ardıl durumların beklentilerini toplar ve buradan \(E_r\) için tek satırlık doğrusal denklemi çözer. En sonda da \(1,5,10,50,100,500\) başlangıç durumlarını boş durum denklemi içinde kullanır ve cevabı sekiz ondalık basamakla yazar.
Sonlu durum uzayında tam \(999\) durum vardır ve her durumda tam \(7\) harf denenir. Bu yüzden geçişleri kurmanın maliyeti \(O(999\cdot7)\), beklentileri çözmenin maliyeti de yine \(O(999\cdot7)\)'dir. Tüm geçiş tablosu saklanırsa bellek \(O(999\cdot7)\), yalnızca beklenti dizisi içinse \(O(999)\) olur. \(999\) ve \(7\) sabit olduğu için pratikte hem zaman hem bellek sabittir.
En cada paso se elige un símbolo de \(\{I,V,X,L,C,D,M,\#\}\). Cada letra romana tiene probabilidad \(0.14\) y el símbolo de parada \(\#\) tiene probabilidad \(0.02\). Una letra solo se añade si la nueva cadena sigue siendo un número romano mínimo y válido; en caso contrario se descarta y el estado no cambia. El proceso termina en el primer \(\#\), y la cadena vacía cuenta como valor \(0\).
Hay que calcular el valor esperado final, redondeado a ocho decimales. Aunque la secuencia aleatoria parece potencialmente infinita, la regla de minimalidad reduce el problema a un conjunto muy pequeño y estructurado de estados.
Las implementaciones en C++, Python y Java convierten el proceso en un sistema finito de esperanzas para la parte inferior a \(1000\), junto con una ecuación adicional para el prefijo ilimitado de \(M\)'s.
Para cada \(r\in\{1,2,\dots,999\}\), sea \(s(r)\) su representación romana mínima y única. Estas \(999\) cadenas forman el espacio de estados finito para toda la parte que no pertenece al bloque inicial de millares.
Para una letra \(\ell\in\{I,V,X,L,C,D,M\}\), se intenta añadir \(\ell\) al final de \(s(r)\). Si la nueva cadena coincide con la representación romana mínima de algún entero \(v\) con \(1\le v\le 999\), entonces el proceso pasa al estado \(v\). Si no, la letra se rechaza y el estado permanece en \(r\).
Así obtenemos una función de transición determinista \(T(r,\ell)\) sobre un conjunto fijo de estados.
Si una letra se acepta, la cadena actual se prolonga hasta otra representación mínima válida más larga. Eso solo puede aumentar el número representado, de modo que todo movimiento aceptado satisface
$$T(r,\ell)>r.$$
Por tanto, el grafo dirigido de transiciones aceptadas sobre \(\{1,\dots,999\}\) es acíclico si ordenamos los estados por su valor. Esa es la razón por la que el sistema puede resolverse por sustitución hacia atrás desde \(999\) hasta \(1\).
Las letras rechazadas no crean estados nuevos; crean auto-bucles.
Sea \(E_r\) el valor esperado final cuando la cadena actual ya es la representación romana mínima de \(r\). En la siguiente extracción, o bien aparece \(\#\) y el proceso termina con valor \(r\), o bien se toma una de las siete letras.
Entonces, para \(1\le r\le 999\),
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
Si exactamente \(q_r\) letras se rechazan en el estado \(r\), esos \(q_r\) términos valen \(E_r\) y pueden llevarse al lado izquierdo:
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
Esta es la identidad lineal principal de la solución.
Los numerales romanos mínimos no están acotados superiormente, porque puede haber cualquier cantidad de \(M\)'s iniciales. En lugar de introducir infinitos estados \(1000,2000,3000,\dots\), se resume esa parte con una sola ecuación.
Sea \(E_0\) la esperanza desde la cadena vacía. Si la primera letra aceptada es \(M\), se añaden \(1000\) unidades inmediatamente y volvemos a la misma situación de “solo hemos visto \(M\)'s al principio”. Si la primera letra aceptada distinta de \(M\) es \(I,V,X,L,C\) o \(D\), entramos en uno de los estados finitos \(1,5,10,50,100,500\).
Condicionando por el primer símbolo, se obtiene
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
Al reorganizar,
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
El coeficiente \(0.86\) es la probabilidad de que el siguiente símbolo no sea \(M\), y \(140\) es la contribución esperada de un solo paso, \(0.14\times1000\).
Tomemos el numeral actual \(X\), que representa \(10\). Añadir \(I,V,X,L,C\) produce \(XI,XV,XX,XL,XC\), todos válidos y mínimos, así que los destinos son \(11,15,20,40,90\).
Añadir \(D\) o \(M\) no da una continuación mínima válida, de modo que esas letras se rechazan. Por eso \(q_{10}=2\) y la ecuación queda
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
Equivalente a
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
Este ejemplo pequeño muestra los dos ingredientes que aparecen en toda la solución: movimientos aceptados hacia delante y auto-bucles producidos por rechazos.
Como todo movimiento aceptado desde \(r\) va a un estado mayor, \(E_{999}\) solo depende de sí mismo, \(E_{998}\) depende de sí mismo y de estados mayores ya conocidos, y así sucesivamente. Por tanto, se pueden calcular
$$E_{999},E_{998},\dots,E_1$$
en ese orden, sin necesidad de métodos iterativos. Una vez conocidos esos \(999\) valores, la ecuación del estado vacío produce inmediatamente la esperanza final.
Las implementaciones en C++, Python y Java generan primero la representación romana mínima de cada entero entre \(0\) y \(999\) usando el sistema voraz estándar de fichas \(1000,900,500,400,\dots,1\). Después, para cada estado \(r\in\{1,\dots,999\}\) y cada una de las siete letras, construyen la cadena candidata, evalúan su valor numérico y aceptan la transición exactamente cuando la cadena candidata coincide con la representación romana mínima de ese valor y permanece dentro del rango \(1\) a \(999\).
Con la tabla de transiciones ya construida, la implementación recorre los estados desde \(999\) hacia abajo. En cada estado cuenta cuántas letras son rechazadas, suma las esperanzas de los sucesores aceptados y resuelve la ecuación lineal reorganizada para \(E_r\). Al final sustituye los seis estados de entrada \(1,5,10,50,100,500\) en la ecuación separada de \(E_0\) y muestra el resultado redondeado a ocho decimales.
La parte finita del espacio de estados tiene exactamente \(999\) estados y en cada uno se prueban exactamente \(7\) letras. Por ello, construir las transiciones cuesta \(O(999\cdot7)\) y resolver las esperanzas cuesta otro \(O(999\cdot7)\). La memoria es \(O(999\cdot7)\) si se guarda la tabla completa de transiciones, u \(O(999)\) para el arreglo de esperanzas. Como \(999\) y \(7\) son constantes fijas, en la práctica el tiempo y la memoria son constantes.
每一步都会从 \(\{I,V,X,L,C,D,M,\#\}\) 中随机抽取一个符号。七个罗马字母的概率都是 \(0.14\)，停止符号 \(\#\) 的概率是 \(0.02\)。如果新抽到的字母拼接到当前字符串后，仍然是一个合法且最简的罗马数字表示，那么这个字母就被接受；否则它会被丢弃，当前字符串保持不变。第一次抽到 \(\#\) 时过程立即停止，空串按数值 \(0\) 处理。
目标是求最终数值的期望，并四舍五入到小数点后八位。看上去这是一个可能无限延续的随机过程，但“必须保持最简罗马表示”这一规则会把它压缩成一个很小而且高度结构化的状态系统。
C++、Python 和 Java 实现都采用同一个思路：先把 \(1000\) 以下的部分变成有限状态期望方程组，再用一条单独的方程处理无限长的前导 \(M\) 串。
对每个 \(r\in\{1,2,\dots,999\}\)，记 \(s(r)\) 为 \(r\) 的唯一最简罗马数字表示。这 \(999\) 个字符串构成了有限状态空间，负责描述“不含任意长千位前缀”的部分。
对于任意字母 \(\ell\in\{I,V,X,L,C,D,M\}\)，我们尝试把 \(\ell\) 追加到当前状态对应的最简表示 \(s(r)\) 后面。如果新串本身正好是某个 \(1\le v\le 999\) 的最简罗马表示，那么状态就转移到 \(v\)。如果不是，则这个字母被拒绝，状态仍然停留在 \(r\)。
于是，罗马数字的合法性规则被编码成了一个确定性的转移函数 \(T(r,\ell)\)。
只要一个字母能被接受，它就会把当前最简罗马串扩展成一个更长的、仍然最简的合法串。这样的操作不可能让表示的整数变小，因此任何被接受的转移都满足
$$T(r,\ell)>r.$$
这意味着，当我们把状态按数值大小排序时，\(\{1,\dots,999\}\) 上所有“真正发生状态变化”的边都会从小指向大，不会形成环。因此整个有限部分的期望方程组可以按 \(999,998,\dots,1\) 的顺序直接回代求解。
被拒绝的字母则不同，它们不会把系统带到新状态，而是形成自环。
设 \(E_r\) 表示“当前字符串已经是 \(r\) 的最简罗马表示时，最终结果的期望值”。下一次抽样只有两类可能：要么抽到 \(\#\)，过程立刻结束并返回当前数值 \(r\)；要么抽到七个字母中的一个。
因此对 \(1\le r\le 999\)，有
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
如果在状态 \(r\) 下恰好有 \(q_r\) 个字母会被拒绝，那么这 \(q_r\) 项实际上就是 \(E_r\) 自身。把它们移到左边后得到
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
这就是程序真正求解的核心线性关系。分母里的 \(1-0.14q_r\) 正是把所有拒绝导致的自环一次性消去后的结果。
最简罗马数字整体上并不是有限集合，因为前面可以有任意多个 \(M\)。如果直接把所有 \(1000,2000,3000,\dots\) 都当作独立状态，状态空间就会变成无限的。实现并没有这么做，而是利用了这些状态的重复结构。
记 \(E_0\) 为从空串出发时的期望值。如果第一个被接受的字母是 \(M\)，那么当前值立刻增加 \(1000\)，并且系统又回到了“目前只看到了若干个前导 \(M\)”的同类局面；也就是说，后续期望仍然是 \(E_0\)。如果第一个被接受的非 \(M\) 字母是 \(I,V,X,L,C,D\) 中的某一个，那么状态就进入有限部分中的 \(1,5,10,50,100,500\)。
按第一次抽样分类，可以写出
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
整理后得到
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
这里的 \(0.86\) 表示“下一次抽到的不是 \(M\)”的概率，而 \(140\) 则来自单步贡献 \(0.14\times1000\)。这一条方程把原本无限的千位前缀链完全压缩成了一个标量未知数。
考虑当前字符串为 \(X\)，也就是数值 \(10\)。如果继续追加 \(I,V,X,L,C\)，分别得到 \(XI,XV,XX,XL,XC\)，这些都是合法且最简的罗马数字，因此会转移到 \(11,15,20,40,90\)。
但如果追加 \(D\) 或 \(M\)，得到的字符串就不再是某个整数的最简罗马表示，所以这两个字母会被拒绝。于是这个状态的拒绝数为 \(q_{10}=2\)，方程为
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
把自环移到左侧后可以写成
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
这个例子完整展示了算法的两个固定模式：一部分字母产生向更大数值的真实转移，另一部分字母因为非法而变成自环。
由于任何被接受的转移都会把状态从 \(r\) 带到更大的数，所以 \(E_{999}\) 只依赖自身，\(E_{998}\) 只依赖自身和已经求出的更大状态，依此类推。于是可以顺序计算
$$E_{999},E_{998},\dots,E_1,$$
完全不需要迭代逼近或矩阵求逆。等到这 \(999\) 个值全部求出后，再代入空状态方程，就能立刻得到最终的期望。
C++、Python 和 Java 实现首先用标准的贪心记号表 \(1000,900,500,400,\dots,1\) 生成 \(0\) 到 \(999\) 每个整数的最简罗马表示。接着，它们对每个状态 \(r\in\{1,\dots,999\}\) 和每个候选字母都进行一次测试：把字母附加到当前字符串末尾，计算新串对应的数值，并且仅当这个候选串与该数值的最简罗马表示完全一致、同时数值仍落在 \(1\) 到 \(999\) 之间时，才把它视为一个有效转移。
构造好转移表之后，实现按照 \(999\) 到 \(1\) 的顺序处理所有状态。对每个状态，先统计有多少个字母会被拒绝，再把所有被接受后继状态的期望值求和，然后直接代入上面的重排方程求出当前 \(E_r\)。最后，把六个有限入口状态 \(1,5,10,50,100,500\) 代入 \(E_0\) 的单独方程，并输出四舍五入到八位小数的结果。
有限状态空间固定为 \(999\) 个状态，每个状态只检查 \(7\) 个字母。因此构造转移表的时间是 \(O(999\cdot7)\)，求解全部期望值的时间也是 \(O(999\cdot7)\)。如果保存完整转移表，空间复杂度为 \(O(999\cdot7)\)；期望数组本身只需要 \(O(999)\) 空间。由于 \(999\) 和 \(7\) 都是固定常数，所以在实际意义上这就是常数时间、常数空间的算法。
На каждом шаге случайно выбирается один символ из множества \(\{I,V,X,L,C,D,M,\#\}\). Каждая римская буква имеет вероятность \(0.14\), а символ остановки \(\#\) имеет вероятность \(0.02\). Буква дописывается только тогда, когда новая строка остаётся корректной минимальной римской записью; иначе она отбрасывается, и текущее состояние не меняется. Процесс заканчивается при первом появлении \(\#\), а пустая строка считается числом \(0\).
Нужно найти математическое ожидание итогового числа с округлением до восьми знаков после запятой. Хотя генерация символов формально может продолжаться бесконечно, условие минимальности сводит задачу к очень маленькой и хорошо устроенной системе состояний.
Реализации на C++, Python и Java строят конечную систему ожиданий для части ниже \(1000\) и одну дополнительную формулу для неограниченного начального блока из \(M\).
Для каждого \(r\in\{1,2,\dots,999\}\) обозначим через \(s(r)\) его единственную минимальную римскую запись. Эти \(999\) строк образуют конечное пространство состояний для всей части, не связанной с произвольной серией тысяч в начале.
Для буквы \(\ell\in\{I,V,X,L,C,D,M\}\) мы пытаемся приписать \(\ell\) к текущей строке \(s(r)\). Если получившаяся строка сама является минимальной римской записью некоторого \(v\) с \(1\le v\le 999\), то происходит переход в состояние \(v\). Иначе буква отвергается, и процесс остаётся в состоянии \(r\).
Так римское правило записи превращается в детерминированное отображение переходов \(T(r,\ell)\) на фиксированном конечном множестве состояний.
Если буква принята, то текущая минимальная запись расширяется до более длинной корректной минимальной записи. Это может только увеличить представляемое число, поэтому для любого принятого перехода выполняется
$$T(r,\ell)>r.$$
Следовательно, ориентированный граф принятых переходов на \(\{1,\dots,999\}\) ацикличен, если упорядочить состояния по числовому значению. Именно поэтому систему ожиданий можно решать обратной подстановкой от \(999\) к \(1\).
Отвергнутые буквы не создают новых состояний, а дают петли в том же состоянии.
Пусть \(E_r\) обозначает ожидаемое итоговое значение, если текущая строка уже равна минимальной римской записи числа \(r\). На следующем шаге либо выпадает \(\#\), и процесс немедленно завершается со значением \(r\), либо выбирается одна из семи букв.
Значит, для \(1\le r\le 999\)
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
Если в состоянии \(r\) ровно \(q_r\) букв отвергаются, то эти \(q_r\) слагаемых просто равны \(E_r\). Перенеся их в левую часть, получаем
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
Это и есть основное линейное соотношение, которое затем решает программа.
Множество минимальных римских записей не ограничено сверху, потому что в начале можно поставить сколько угодно символов \(M\). Вместо введения бесконечного числа состояний \(1000,2000,3000,\dots\) этот фрагмент сворачивается в одну скалярную формулу.
Обозначим через \(E_0\) математическое ожидание при старте с пустой строки. Если первая принятая буква равна \(M\), то значение сразу увеличивается на \(1000\), а дальнейшая ситуация снова совпадает с тем же состоянием “мы пока видели только ведущие \(M\)”. Если же первой принятой буквой, отличной от \(M\), становится одна из \(I,V,X,L,C,D\), процесс попадает в одно из конечных состояний \(1,5,10,50,100,500\).
Разбивая по первому шагу, получаем
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
После преобразования выходит
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
Коэффициент \(0.86\) равен вероятности того, что следующий символ не окажется \(M\), а число \(140\) есть одношаговый вклад \(0.14\times1000\).
Рассмотрим текущее число \(X\), то есть значение \(10\). Приписывание \(I,V,X,L,C\) даёт строки \(XI,XV,XX,XL,XC\), и все они являются корректными минимальными римскими записями. Значит, переходы идут в состояния \(11,15,20,40,90\).
Приписывание \(D\) или \(M\) не даёт допустимого минимального продолжения, поэтому эти буквы отвергаются. Следовательно, \(q_{10}=2\), и уравнение принимает вид
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
Или, что то же самое,
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
Этот пример наглядно показывает две постоянные составляющие всей схемы: разрешённые переходы к большим значениям и петли, возникающие из-за отказов.
Так как любой принятый переход из \(r\) ведёт только в большее состояние, величина \(E_{999}\) зависит лишь от самой себя, \(E_{998}\) зависит от себя и уже вычисленных больших состояний и так далее. Поэтому значения
$$E_{999},E_{998},\dots,E_1$$
можно вычислить последовательно именно в этом порядке, без итерационных методов и без обращения больших матриц. После этого отдельная формула для \(E_0\) немедленно даёт окончательный ответ.
Реализации на C++, Python и Java сначала строят минимальную римскую запись для каждого числа от \(0\) до \(999\) с помощью стандартного жадного набора токенов \(1000,900,500,400,\dots,1\). Затем для каждого состояния \(r\in\{1,\dots,999\}\) и каждой из семи букв они формируют строку-кандидат, вычисляют её числовое значение и принимают переход только в том случае, если кандидат в точности совпадает с минимальной римской записью своего значения и остаётся в диапазоне от \(1\) до \(999\).
После построения таблицы переходов программа проходит состояния от \(999\) вниз. Для каждого состояния она подсчитывает число отвергаемых букв, суммирует ожидания принятых последователей и сразу решает переставленное линейное уравнение для \(E_r\). В конце шесть входных состояний \(1,5,10,50,100,500\) подставляются в отдельную формулу для \(E_0\), после чего выводится результат с восьмью знаками после запятой.
Конечная часть пространства состояний содержит ровно \(999\) состояний, и в каждом проверяются ровно \(7\) букв. Значит, построение переходов требует \(O(999\cdot7)\), а вычисление всех ожиданий ещё \(O(999\cdot7)\). По памяти это \(O(999\cdot7)\) при хранении полной таблицы переходов или \(O(999)\) для массива ожиданий. Поскольку \(999\) и \(7\) являются фиксированными константами, на практике это алгоритм с постоянным временем и постоянной памятью.
في كل خطوة نختار رمزًا من المجموعة \(\{I,V,X,L,C,D,M,\#\}\). احتمال كل حرف روماني هو \(0.14\)، واحتمال رمز التوقف \(\#\) هو \(0.02\). لا يُضاف الحرف المختار إلا إذا بقيت السلسلة الناتجة تمثيلًا رومانيًا أدنى وصحيحًا؛ وإذا لم يتحقق ذلك يُرفض الحرف وتبقى السلسلة الحالية كما هي. تتوقف العملية عند أول ظهور للرمز \(\#\)، وتُحسب السلسلة الفارغة على أنها القيمة \(0\).
المطلوب هو إيجاد القيمة المتوقعة للعدد النهائي مع التقريب إلى ثمانية منازل عشرية. وعلى الرغم من أن السلسلة العشوائية قد تبدو غير منتهية، فإن شرط الحفاظ على الصيغة الرومانية الدنيا يحول المسألة إلى نظام حالات صغير ومنظم.
تعامل تطبيقات C++ وPython وJava المسألة على أنها نظام توقعات منتهٍ للجزء الواقع تحت \(1000\)، مع معادلة إضافية مستقلة لمعالجة المقدمة غير المحدودة من الحرف \(M\).
لكل \(r\in\{1,2,\dots,999\}\)، لنرمز بـ \(s(r)\) إلى التمثيل الروماني الأدنى والوحيد للعدد \(r\). هذه السلاسل البالغ عددها \(999\) تشكل فضاء الحالات المنتهي لكل ما لا يحتاج إلى مقدمة آلاف طويلة.
إذا أخذنا حرفًا \(\ell\in\{I,V,X,L,C,D,M\}\)، فإننا نحاول إلحاقه بنهاية السلسلة الحالية \(s(r)\). فإذا كانت السلسلة الناتجة هي نفسها التمثيل الروماني الأدنى لعدد \(v\) يحقق \(1\le v\le 999\)، انتقلنا إلى الحالة \(v\). أما إذا لم تكن كذلك فإن الحرف يُرفض ونبقى في الحالة \(r\).
بهذه الطريقة تتحول قاعدة الأرقام الرومانية إلى دالة انتقال حتمية \(T(r,\ell)\) على مجموعة حالات ثابتة.
عندما يُقبل حرف ما، فإنه يوسّع التمثيل الروماني الأدنى الحالي إلى تمثيل أدنى أطول وما زال صحيحًا. وهذا لا يمكن أن يُنقص العدد المُمثَّل، ولذلك يحقق كل انتقال مقبول العلاقة
$$T(r,\ell)>r.$$
إذن فإن الرسم الموجّه للانتقالات المقبولة على \(\{1,\dots,999\}\) يكون خاليًا من الدورات إذا رتبنا الحالات بحسب قيمها. ولهذا يمكن حل نظام التوقعات بالرجوع من \(999\) نزولًا إلى \(1\).
أما الحروف المرفوضة فلا تنشئ حالات جديدة، بل تُنتج حلقات ذاتية.
ليكن \(E_r\) هو القيمة المتوقعة النهائية عندما تكون السلسلة الحالية بالفعل هي التمثيل الروماني الأدنى للعدد \(r\). في السحب التالي إما أن يظهر الرمز \(\#\) فتنتهي العملية بالقيمة \(r\)، أو يُسحب أحد الحروف السبعة.
لذلك، عندما \(1\le r\le 999\)، نحصل على
$$E_r=0.02\,r+0.14\sum_{\ell\in\{I,V,X,L,C,D,M\}} E_{T(r,\ell)}.$$
إذا كان عدد الحروف المرفوضة في الحالة \(r\) هو \(q_r\)، فإن هذه الحدود \(q_r\) تساوي \(E_r\) نفسه لأنها حلقات ذاتية. وبعد نقلها إلى الطرف الأيسر يصبح
$$E_r=\frac{0.02\,r+0.14\sum_{\ell:\,T(r,\ell)\ne r} E_{T(r,\ell)}}{1-0.14\,q_r}.$$
وهذه هي العلاقة الخطية الأساسية التي تعتمد عليها جميع التطبيقات.
مجموعة التمثيلات الرومانية الدنيا ليست منتهية من الأعلى، لأن وجود أي عدد من الأحرف \(M\) في البداية مسموح به. بدلًا من إنشاء عدد لا نهائي من الحالات \(1000,2000,3000,\dots\)، تُختصر هذه البنية في معادلة واحدة.
لنرمز بـ \(E_0\) إلى التوقع عند البدء من السلسلة الفارغة. إذا كان أول حرف مقبول هو \(M\)، فإننا نضيف \(1000\) فورًا ثم نعود إلى الحالة البنيوية نفسها: ما زلنا داخل مقدمة تتكون فقط من أحرف \(M\). أما إذا كان أول حرف مقبول مختلفًا عن \(M\) ومن المجموعة \(I,V,X,L,C,D\)، فإننا ندخل إحدى الحالات المنتهية \(1,5,10,50,100,500\).
بالتكييف على أول سحب نحصل على
$$E_0=0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}+(1000+E_0)\right).$$
وبإعادة الترتيب نحصل على
$$0.86\,E_0=140+0.14\left(E_1+E_5+E_{10}+E_{50}+E_{100}+E_{500}\right).$$
المعامل \(0.86\) هو احتمال أن لا يكون الرمز التالي هو \(M\)، أما الحد \(140\) فهو المساهمة المتوقعة من خطوة واحدة \(0.14\times1000\).
لنأخذ السلسلة الحالية \(X\)، أي القيمة \(10\). إذا ألحقنا بها \(I,V,X,L,C\) حصلنا على \(XI,XV,XX,XL,XC\)، وجميعها تمثيلات رومانية دنيا صحيحة، ولذلك تنتقل العملية إلى الحالات \(11,15,20,40,90\).
أما إلحاق \(D\) أو \(M\) فلا ينتج استمرارًا أدنى صحيحًا، ولذلك يُرفض هذان الحرفان. وعليه يكون \(q_{10}=2\)، وتصبح المعادلة
$$E_{10}=0.02\cdot10+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}+2E_{10}\right).$$
وبصورة مكافئة
$$0.72\,E_{10}=0.2+0.14\left(E_{11}+E_{15}+E_{20}+E_{40}+E_{90}\right).$$
هذا المثال الصغير يكشف النمطين اللذين يتكرران في الحل كله: انتقالات مقبولة إلى قيم أكبر، وحلقات ذاتية ناتجة عن الحروف المرفوضة.
بما أن كل انتقال مقبول من الحالة \(r\) يذهب إلى حالة أكبر منها، فإن \(E_{999}\) يعتمد فقط على نفسه، و\(E_{998}\) يعتمد على نفسه وعلى حالات أكبر سبق حسابها، وهكذا. لذلك يمكن حساب
$$E_{999},E_{998},\dots,E_1$$
مباشرة بهذا الترتيب من غير حاجة إلى طرق عددية تكرارية. وبعد معرفة هذه القيم \(999\)، تعطي معادلة الحالة الفارغة التوقع النهائي فورًا.
تبدأ تطبيقات C++ وPython وJava ببناء التمثيل الروماني الأدنى لكل عدد من \(0\) إلى \(999\) باستخدام جدول الترميز الجشع القياسي \(1000,900,500,400,\dots,1\). بعد ذلك تختبر كل حالة \(r\in\{1,\dots,999\}\) مع كل واحد من الحروف السبعة: تُنشأ السلسلة المرشحة، ثم تُحسب قيمتها العددية، ولا يُقبل الانتقال إلا إذا كانت هذه السلسلة مساوية تمامًا للتمثيل الروماني الأدنى لتلك القيمة وبقيت القيمة ضمن المجال من \(1\) إلى \(999\).
بعد بناء جدول الانتقالات، تعالج التطبيقات الحالات من \(999\) نزولًا. في كل حالة تُحصي عدد الحروف المرفوضة، ثم تجمع توقعات الحالات اللاحقة المقبولة، ثم تحل المعادلة الخطية المعاد ترتيبها للحصول على \(E_r\). وفي النهاية تُعوَّض الحالات الابتدائية الست \(1,5,10,50,100,500\) في معادلة \(E_0\) المستقلة، ثم تُطبع النتيجة مقربة إلى ثمانية منازل عشرية.
الجزء المنتهي من فضاء الحالات يحتوي على \(999\) حالة بالضبط، وفي كل حالة نختبر \(7\) أحرف فقط. لذا فإن بناء الانتقالات يكلف \(O(999\cdot7)\)، كما أن حل جميع التوقعات يكلف \(O(999\cdot7)\) أيضًا. وإذا خُزِّن جدول الانتقالات كاملًا فالاستهلاك هو \(O(999\cdot7)\)، أما مصفوفة التوقعات نفسها فتحتاج \(O(999)\) فقط. وبما أن \(999\) و\(7\) ثوابت، فإن الزمن والذاكرة ثابتان عمليًا.