The input file contains 1000 Roman numerals. Every numeral is valid, but some are not written in shortest form. The task is to rewrite each line in canonical minimal Roman notation and add up how many characters are saved.
If \(s\) is one numeral, let \(\operatorname{val}(s)\) be its integer value and let \(R(n)\) be the minimal Roman representation of the integer \(n\). The required total is therefore
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
So the entire problem reduces to two precise operations on a single Roman string: evaluate it correctly, then reconstruct the same number in minimal form.
The Roman alphabet is \(\{M,D,C,L,X,V,I\}\) with values \(1000,500,100,50,10,5,1\). Minimal Roman numerals also use the six subtractive pairs \(IV, IX, XL, XC, CD,\) and \(CM\). The implementations solve the problem entirely through these local value rules and the decimal block structure of Roman notation.
Write a Roman string as \(s=s_1s_2\cdots s_m\), and let \(v(s_i)\) denote the value of the \(i\)-th symbol. In a valid numeral, a symbol contributes negatively exactly when it is the smaller member of a subtractive pair; otherwise it contributes positively. That gives the evaluation rule
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ and } v(s_i)<v(s_{i+1}),\\ 1,& \text{otherwise}. \end{cases}$$
This is why the parser only needs one-character lookahead. A rise in value means subtraction, while every non-rise means addition. For example,
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
To rebuild a number in shortest form, the implementations use the descending token list
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
Starting from an integer \(n\), repeatedly take the largest token whose value does not exceed the current remainder, append its Roman symbol, and subtract its value. Because the table already contains the subtractive forms, the output is produced directly in canonical notation.
The key fact is that Roman numerals split naturally by decimal place. If
$$n=1000a+100b+10c+d,$$
then the minimal Roman numeral is obtained by concatenating a thousands block, a hundreds block, a tens block, and a ones block.
For a place whose symbols are \((u,f,t)\), meaning one, five, and ten times that place value, the minimal digit blocks satisfy
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
Thus the ones place uses \((I,V,X)\), the tens place uses \((X,L,C)\), and the hundreds place uses \((C,D,M)\). The thousands block is simply \(a\) copies of \(M\).
No shorter valid block exists for any digit. The digit 4 is best written as \(IV\), not \(IIII\); the digit 9 is best written as \(IX\), not \(VIIII\); the digit 8 is best written as \(VIII\), not a longer additive alternative. Since the decimal places do not interfere with one another, minimizing each block separately minimizes the whole numeral.
The descending table \(\mathcal{T}\) is exactly a procedural version of this place-value decomposition. After all thousands are removed, the remainder is below 1000, so the next token choices determine the hundreds digit, then the tens digit, then the ones digit.
Consider the non-minimal numeral \(MDCCCCLXXXXVIIII\). Its value is
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
Now decompose \(1999\) by decimal place:
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
The minimal blocks are therefore
$$M,\qquad CM,\qquad XC,\qquad IX,$$
so the canonical numeral is \(MCMXCIX\). The original string has length \(16\), the minimal string has length \(7\), and this one line saves
$$16-7=9$$
characters. The checkpoint-style simplifications \(VIIII\to IX\) and \(LXXXX\to XC\) are smaller instances of the same rule.
Once \(R(n)\) is defined by the minimal reconstruction rule, the final answer is just
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Each line is independent of every other line. There is no hidden global combinatorics here; the entire mathematics lives inside correct Roman evaluation and minimal Roman re-encoding.
The C++, Python, and Java implementations first map each Roman character to its integer value. They scan the string from left to right and use one-step lookahead: if the next symbol is larger, the current value is subtracted; otherwise it is added. This computes \(\operatorname{val}(s)\) in a single pass.
After obtaining the integer value, the implementation walks through the fixed table \(\mathcal{T}\) from 1000 down to 1. For each entry, it appends the corresponding Roman token as many times as possible before moving to the next smaller token. Because \(CM, CD, XC, XL, IX,\) and \(IV\) already appear in the table, the produced string is the minimal Roman numeral itself, not merely an equivalent one.
For each input line, the implementation compares the length of the original numeral with the length of the reconstructed minimal numeral and adds the difference to a running total. The three language versions differ only in syntax; the algorithmic structure is the same.
If the input contains numerals \(s_1,\dots,s_N\) with total length \(L_{\text{tot}}=\sum |s_i|\), then parsing costs \(O(L_{\text{tot}})\), because every input character is examined once. Reconstruction is also linear in the length of the produced minimal numerals, and the token table has fixed size 13.
For this problem the numerals are short, so the constants are tiny. Asymptotically the whole computation is linear in the total amount of input text, and the extra memory usage is \(O(1)\) beyond the current line and the minimal string being built.
Die Eingabedatei enthält 1000 römische Zahlen. Jede davon ist gültig, aber nicht immer in kürzester Form geschrieben. Gesucht ist, wie viele Zeichen insgesamt eingespart werden, wenn jede Zeile in die kanonische Minimaldarstellung umgeschrieben wird.
Ist \(s\) ein römischer String, so sei \(\operatorname{val}(s)\) sein Zahlenwert und \(R(n)\) die minimale römische Darstellung der Zahl \(n\). Dann lautet die gesuchte Summe
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Damit zerfällt das gesamte Problem in zwei genaue Teilaufgaben: einen römischen String korrekt auswerten und dieselbe Zahl anschließend minimal wieder codieren.
Das römische Alphabet ist \(\{M,D,C,L,X,V,I\}\) mit den Werten \(1000,500,100,50,10,5,1\). Zur Minimaldarstellung gehören außerdem die sechs Subtraktionspaare \(IV, IX, XL, XC, CD,\) und \(CM\). Die Implementierungen verwenden genau diese lokalen Regeln und die Stellenwertstruktur römischer Zahlen.
Schreibe einen römischen String als \(s=s_1s_2\cdots s_m\), und bezeichne mit \(v(s_i)\) den Wert des \(i\)-ten Symbols. In einer gültigen Zahl trägt ein Symbol genau dann negativ bei, wenn es der kleinere Teil eines Subtraktionspaares ist; sonst trägt es positiv bei. Daraus folgt die Auswertungsformel
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ und } v(s_i)<v(s_{i+1}),\\ 1,& \text{sonst}. \end{cases}$$
Darum braucht der Parser nur einen Blick auf das nächste Zeichen. Ein Anstieg des Wertes bedeutet Subtraktion, jeder Nichtanstieg bedeutet Addition. Zum Beispiel gilt
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
Für die Rückumwandlung in die kürzeste Form verwenden die Implementierungen die absteigende Tabelle
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
Ausgehend von einer ganzen Zahl \(n\) wählt man immer das größte Token, dessen Wert den aktuellen Rest nicht überschreitet, hängt das zugehörige Symbol an und zieht den Wert ab. Weil die subtraktiven Formen bereits in der Tabelle stehen, entsteht die kanonische Schreibweise direkt.
Der entscheidende strukturelle Punkt ist die Zerlegung nach Dezimalstellen. Gilt
$$n=1000a+100b+10c+d,$$
dann setzt sich die minimale römische Zahl aus einem Tausenderblock, einem Hunderterblock, einem Zehnerblock und einem Einerblock zusammen.
Für eine Stelle mit Symbolen \((u,f,t)\), also eins-, fünf- und zehnfacher Stellenwert, erfüllen die minimalen Ziffernblöcke
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
Die Einerstelle verwendet also \((I,V,X)\), die Zehnerstelle \((X,L,C)\) und die Hunderterstelle \((C,D,M)\). Der Tausenderblock besteht einfach aus \(a\) aufeinanderfolgenden \(M\).
Für keine Ziffer gibt es einen kürzeren gültigen Block. Die 4 schreibt man optimal als \(IV\) und nicht als \(IIII\); die 9 optimal als \(IX\) und nicht als \(VIIII\); die 8 optimal als \(VIII\). Da sich die Dezimalstellen nicht gegenseitig stören, erhält man eine globale Minimaldarstellung, indem man jeden Stellenblock für sich minimiert.
Die absteigende Tabelle \(\mathcal{T}\) ist genau die algorithmische Form dieser Stellenwertzerlegung. Nachdem alle Tausender entfernt wurden, ist der Rest kleiner als 1000; damit bestimmen die nächsten Tokens die Hunderterstelle, dann die Zehnerstelle und schließlich die Einerstelle.
Betrachte die nicht minimale Zahl \(MDCCCCLXXXXVIIII\). Ihr Wert ist
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
Zerlegt nach Dezimalstellen gilt
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
Die minimalen Blöcke sind also
$$M,\qquad CM,\qquad XC,\qquad IX,$$
und damit lautet die kanonische Form \(MCMXCIX\). Der ursprüngliche String hat Länge \(16\), die Minimalform Länge \(7\), also spart diese eine Zeile
$$16-7=9$$
Zeichen. Die Vereinfachungen \(VIIII\to IX\) und \(LXXXX\to XC\) sind nur kleinere Spezialfälle derselben Regel.
Sobald \(R(n)\) durch die Minimalregel festliegt, ist die gesuchte Gesamtgröße einfach
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Jede Zeile wird unabhängig von allen anderen verarbeitet. Es gibt keine globale Kombinatorik; die gesamte Mathematik steckt in korrekter Auswertung und minimaler Neukodierung eines einzelnen römischen Strings.
Die Implementierungen in C++, Python und Java ordnen jedem römischen Zeichen zunächst seinen Zahlenwert zu. Dann wird der String von links nach rechts durchlaufen: Ist das nächste Symbol größer, wird der aktuelle Wert subtrahiert, sonst addiert. So erhält man \(\operatorname{val}(s)\) in einem einzigen Durchgang.
Nach der Auswertung wird die feste Tabelle \(\mathcal{T}\) von 1000 bis 1 durchlaufen. Für jeden Eintrag hängt die Implementierung das zugehörige Token so oft wie möglich an, bevor sie zum nächsten kleineren Wert übergeht. Weil \(CM, CD, XC, XL, IX,\) und \(IV\) bereits in der Tabelle stehen, ist der erzeugte String unmittelbar die minimale römische Darstellung.
Für jede Eingabezeile wird die Länge der ursprünglichen Zahl mit der Länge der rekonstruierten Minimalform verglichen; die Differenz fließt in eine laufende Summe ein. Die drei Sprachversionen unterscheiden sich nur syntaktisch, nicht algorithmisch.
Besteht die Eingabe aus Zahlen \(s_1,\dots,s_N\) mit Gesamtlänge \(L_{\text{tot}}=\sum |s_i|\), dann kostet das Parsen \(O(L_{\text{tot}})\), weil jedes Zeichen genau einmal betrachtet wird. Auch die Rekonstruktion ist linear in der Länge der erzeugten Minimalformen, und die Tokentabelle hat feste Größe 13.
Für diese Aufgabe sind die römischen Zahlen kurz, daher sind die Konstanten sehr klein. Asymptotisch ist die gesamte Rechnung linear in der Gesamtmenge des Eingabetextes, und der zusätzliche Speicherverbrauch beträgt \(O(1)\) über die aktuelle Zeile und den gerade aufgebauten Minimalstring hinaus.
Girdi dosyasında 1000 Roma rakamı vardır. Her satır geçerlidir, fakat her zaman en kısa biçimde yazılmış değildir. Amaç, her satırı aynı tam sayının kanonik en kısa Roma gösterimine dönüştürmek ve toplam kaç karakter tasarruf edildiğini bulmaktır.
\(s\) bir Roma rakamı olsun. \(\operatorname{val}(s)\), bu yazımın sayısal değeri; \(R(n)\) ise \(n\) sayısının minimal Roma gösterimi olsun. O zaman aranan toplam
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr)$$
şeklindedir. Dolayısıyla bütün problem tek bir satır üzerinde yapılan iki işlemdir: doğru sayısal değeri bulmak ve aynı sayıyı en kısa Roma biçimiyle yeniden yazmak.
Roma alfabesi \(\{M,D,C,L,X,V,I\}\) kümesinden oluşur ve değerler sırasıyla \(1000,500,100,50,10,5,1\) olur. Minimal gösterimde ayrıca altı çıkarma çifti kullanılır: \(IV, IX, XL, XC, CD,\) ve \(CM\). Uygulamalar tamamen bu yerel değer kuralları ile Roma yazımının onluk basamak yapısına dayanır.
Bir Roma dizisini \(s=s_1s_2\cdots s_m\) şeklinde yazalım ve \(v(s_i)\) ile \(i\). sembolün değerini gösterelim. Geçerli bir Roma yazımında bir sembol tam olarak yalnızca kendisinden büyük bir sembolün hemen önündeyse negatif katkı yapar; bunun dışındaki her durumda pozitif katkı yapar. Bu da şu formülü verir:
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ ve } v(s_i)<v(s_{i+1}),\\ 1,& \text{aksi halde}. \end{cases}$$
Bu yüzden çözümde tek karakter ileri bakmak yeterlidir. Değer yükseliyorsa çıkarma, yükselmiyorsa toplama yapılır. Örneğin
$$MCMXCIX=1000-100+1000-10+100-1+10=1999$$
olur.
Bir sayıyı en kısa biçime çevirmek için uygulamalar şu azalan tabloyu kullanır:
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
Bir \(n\) tam sayısından başlanır, kalan değeri aşmayan en büyük token seçilir, ilgili sembol eklenir ve değeri çıkarılır. Çıkarma gösterimleri tabloda baştan bulunduğu için çıktı doğrudan kanonik minimal biçimde oluşur.
Asıl yapısal gerçek, Roma rakamlarının onluk basamaklara ayrılmasıdır. Eğer
$$n=1000a+100b+10c+d$$
ise minimal Roma yazımı bir binler bloğu, bir yüzler bloğu, bir onlar bloğu ve birler bloğunun ardışık birleştirilmesiyle elde edilir.
\((u,f,t)\) sembolleri sırasıyla o basamağın bir, beş ve on katını göstersin. O zaman en kısa rakam blokları
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr)$$
eşitliğini sağlar. Buna göre birler basamağı \((I,V,X)\), onlar basamağı \((X,L,C)\), yüzler basamağı \((C,D,M)\) ile yazılır. Binler bloğu ise yalnızca art arda gelen \(a\) tane \(M\)'dir.
Hiçbir rakam için daha kısa geçerli bir blok yoktur. 4 en iyi \(IV\) ile, 9 en iyi \(IX\) ile, 8 ise \(VIII\) ile yazılır. Basamaklar birbirine karışmadığı için her basamağı ayrı ayrı minimize etmek tüm sayının da minimal olmasını sağlar.
Azalan \(\mathcal{T}\) tablosu bu basamak ayrışımının algoritmik karşılığıdır. Önce bütün binler temizlenir, kalan 1000'den küçülür; sonra yüzler, ardından onlar ve en son birler belirlenir.
Minimal olmayan \(MDCCCCLXXXXVIIII\) yazımını ele alalım. Bunun değeri
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999$$
olur. Şimdi \(1999\) sayısını basamaklarına ayıralım:
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
Minimal bloklar sırasıyla
$$M,\qquad CM,\qquad XC,\qquad IX$$
olduğu için kanonik yazım \(MCMXCIX\) olur. İlk dizenin uzunluğu \(16\), minimal dizenin uzunluğu \(7\) olduğundan bu tek satırda
$$16-7=9$$
karakter tasarruf edilir. \(VIIII\to IX\) ve \(LXXXX\to XC\) dönüşümleri aynı kuralın daha küçük örnekleridir.
\(R(n)\) minimal yeniden yazım kuralıyla tanımlandıktan sonra nihai cevap yalnızca
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr)$$
ifadesidir. Her satır diğerlerinden bağımsızdır. Yani problemde gizli bir küresel kombinatorik yoktur; bütün matematik tek bir Roma yazımını doğru yorumlayıp minimal biçimde yeniden üretmektir.
C++, Python ve Java uygulamaları önce her Roma sembolünü tamsayı değerine eşler. Ardından dize soldan sağa dolaşılır: sonraki sembol daha büyükse mevcut değer çıkarılır, değilse eklenir. Böylece \(\operatorname{val}(s)\) tek geçişte hesaplanır.
Tam sayı değeri elde edildikten sonra uygulama sabit \(\mathcal{T}\) tablosunu 1000'den 1'e doğru gezer. Her giriş için, mümkün olduğu kadar çok aynı token eklenir ve sonra bir küçüğüne geçilir. Tabloda \(CM, CD, XC, XL, IX,\) ve \(IV\) zaten bulunduğundan üretilen dize doğrudan minimal Roma gösterimidir.
Her satırda özgün yazımın uzunluğu ile yeniden üretilen minimal yazımın uzunluğu karşılaştırılır ve fark toplam cevaba eklenir. Üç dildeki uygulamalar yalnızca söz dizimi bakımından farklıdır; algoritma aynıdır.
Girdi \(s_1,\dots,s_N\) rakamlarından oluşsun ve toplam uzunluk \(L_{\text{tot}}=\sum |s_i|\) olsun. Ayrıştırma maliyeti \(O(L_{\text{tot}})\)'dir; çünkü her giriş karakteri tam bir kez incelenir. Yeniden yazım da üretilen minimal dizelerin uzunluğuna göre doğrusaldır ve token tablosunun boyutu sabit \(13\)'tür.
Bu problemde Roma rakamları kısa olduğu için sabit katsayılar çok küçüktür. Asimptotik olarak bütün hesap toplam giriş metni uzunluğunda doğrusaldır ve ek bellek kullanımı mevcut satır ile oluşturulan minimal dize dışında \(O(1)\)'dir.
El archivo de entrada contiene 1000 números romanos. Cada uno es válido, pero algunos no están escritos en su forma más corta. La tarea consiste en reescribir cada línea en la notación romana mínima canónica y sumar cuántos caracteres se ahorran en total.
Si \(s\) es un numeral romano, sea \(\operatorname{val}(s)\) su valor entero y sea \(R(n)\) la representación romana mínima del entero \(n\). Entonces la cantidad buscada es
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Por tanto, todo el problema se reduce a dos operaciones exactas sobre una sola cadena romana: evaluarla correctamente y reconstruir el mismo número en forma mínima.
El alfabeto romano es \(\{M,D,C,L,X,V,I\}\), con valores \(1000,500,100,50,10,5,1\). La forma mínima también usa las seis parejas sustractivas \(IV, IX, XL, XC, CD,\) y \(CM\). Las implementaciones se apoyan por completo en esas reglas locales y en la estructura decimal de la escritura romana.
Escribamos una cadena romana como \(s=s_1s_2\cdots s_m\), y sea \(v(s_i)\) el valor del símbolo \(i\)-ésimo. En un numeral válido, un símbolo contribuye negativamente exactamente cuando es el miembro menor de una pareja sustractiva; en cualquier otro caso contribuye positivamente. Eso produce la fórmula
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ y } v(s_i)<v(s_{i+1}),\\ 1,& \text{en otro caso}. \end{cases}$$
Por eso el análisis solo necesita mirar un carácter hacia delante. Si el valor sube, se resta; si no sube, se suma. Por ejemplo,
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
Para reconstruir un número en su forma más corta, las implementaciones usan la lista descendente
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
Partiendo de un entero \(n\), se toma repetidamente el mayor token cuyo valor no supera al residuo actual, se añade su símbolo y se resta su valor. Como la tabla ya contiene las formas sustractivas, la salida queda construida directamente en notación canónica.
El hecho estructural clave es que los números romanos se separan por posiciones decimales. Si
$$n=1000a+100b+10c+d,$$
entonces el numeral romano mínimo se obtiene concatenando un bloque de millares, un bloque de centenas, un bloque de decenas y un bloque de unidades.
Para una posición cuyos símbolos son \((u,f,t)\), es decir, una, cinco y diez veces ese valor posicional, los bloques mínimos de dígitos cumplen
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
Así, las unidades usan \((I,V,X)\), las decenas usan \((X,L,C)\) y las centenas usan \((C,D,M)\). El bloque de millares es simplemente \(a\) copias consecutivas de \(M\).
No existe un bloque válido más corto para ningún dígito. El 4 se escribe mejor como \(IV\), no como \(IIII\); el 9 como \(IX\), no como \(VIIII\); el 8 como \(VIII\). Como las distintas posiciones no interfieren entre sí, minimizar cada bloque por separado minimiza todo el numeral.
La tabla descendente \(\mathcal{T}\) es exactamente la versión procedimental de esta descomposición por posiciones. Una vez retirados todos los millares, el residuo queda por debajo de 1000; a partir de ahí se fijan las centenas, luego las decenas y por último las unidades.
Consideremos el numeral no mínimo \(MDCCCCLXXXXVIIII\). Su valor es
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
Ahora descomponemos \(1999\) por posiciones:
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
Los bloques mínimos son entonces
$$M,\qquad CM,\qquad XC,\qquad IX,$$
de modo que la forma canónica es \(MCMXCIX\). La cadena original tiene longitud \(16\), la mínima tiene longitud \(7\), y esta sola línea ahorra
$$16-7=9$$
caracteres. Las simplificaciones \(VIIII\to IX\) y \(LXXXX\to XC\) son casos más pequeños de la misma idea.
Una vez definida \(R(n)\) mediante la regla de reconstrucción mínima, la respuesta final es simplemente
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Cada línea se procesa de forma independiente. No hay una combinatoria global escondida; toda la matemática del problema está en evaluar bien un numeral romano y volver a escribirlo de manera mínima.
Las implementaciones en C++, Python y Java asignan primero a cada carácter romano su valor entero. Después recorren la cadena de izquierda a derecha con una mirada de un paso: si el siguiente símbolo es mayor, el valor actual se resta; en caso contrario se suma. Así se obtiene \(\operatorname{val}(s)\) en una sola pasada.
Una vez calculado el entero, la implementación recorre la tabla fija \(\mathcal{T}\) desde 1000 hasta 1. Para cada entrada, añade el token romano correspondiente tantas veces como sea posible antes de pasar al siguiente valor menor. Como \(CM, CD, XC, XL, IX,\) e \(IV\) ya están en la tabla, la cadena producida es el numeral romano mínimo mismo.
Para cada línea de entrada, la implementación compara la longitud del numeral original con la longitud del numeral mínimo reconstruido y suma la diferencia a un acumulador. Las tres versiones del programa solo cambian en la sintaxis superficial; el procedimiento matemático es idéntico.
Si la entrada contiene numerales \(s_1,\dots,s_N\) con longitud total \(L_{\text{tot}}=\sum |s_i|\), entonces el análisis cuesta \(O(L_{\text{tot}})\), porque cada carácter de entrada se examina una vez. La reconstrucción también es lineal en la longitud de los numerales mínimos generados, y la tabla de tokens tiene tamaño fijo 13.
En esta tarea los numerales romanos son cortos, así que los factores constantes son muy pequeños. Asintóticamente todo el algoritmo es lineal en la cantidad total de texto de entrada, y la memoria extra es \(O(1)\) más allá de la línea actual y la cadena mínima que se está construyendo.
输入文件包含 1000 个罗马数字。每一行都是合法写法，但并不一定已经是最短形式。题目的目标是把每一行都改写成同一个整数的规范最短罗马表示，并把所有节省下来的字符数加总起来。
若 \(s\) 表示某一行罗马数字，记 \(\operatorname{val}(s)\) 为它对应的整数值，记 \(R(n)\) 为整数 \(n\) 的最小罗马表示，则所求总量正是
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
因此整道题实际上只有两个核心动作：先把一个罗马字符串正确解释成整数，再把这个整数重新写成最短的罗马形式。
罗马数字的字母表为 \(\{M,D,C,L,X,V,I\}\)，其数值依次为 \(1000,500,100,50,10,5,1\)。最小写法还要使用六个减法对：\(IV, IX, XL, XC, CD,\) 和 \(CM\)。实现中的全部数学内容都来自这组局部规则，以及罗马数字按十进制位分块的结构。
把一个罗马字符串写成 \(s=s_1s_2\cdots s_m\)，并用 \(v(s_i)\) 表示第 \(i\) 个字符的数值。在合法罗马数字中，一个字符恰好只会在它作为减法对中较小的那个符号时贡献负值；其余情况下都贡献正值。因此有
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ 且 } v(s_i)<v(s_{i+1}),\\ 1,& \text{否则}. \end{cases}$$
这正是三个实现都只需要“向前看一个字符”的原因。若下一个字符更大，就做减法；否则就做加法。例如
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
要把整数重建成最短罗马写法，实现使用如下按数值从大到小排列的表：
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
从整数 \(n\) 出发，反复选择不超过当前余数的最大令牌，附加其罗马记号，再减去对应数值。因为表中已经直接包含了减法形式，所以输出不是“等价写法”而是直接得到规范最短写法。
关键的结构事实是：罗马数字天然按十进制位拆开处理。如果
$$n=1000a+100b+10c+d,$$
那么最小罗马表示就是“千位块 + 百位块 + 十位块 + 个位块”的串接。
对于某一位，若 \((u,f,t)\) 分别表示这一位的 1 倍、5 倍和 10 倍符号，则最短数字块满足
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
于是个位使用 \((I,V,X)\)，十位使用 \((X,L,C)\)，百位使用 \((C,D,M)\)。千位块则只是连续的 \(a\) 个 \(M\)。
任何一个数字都不存在更短的合法块。比如 4 的最佳写法是 \(IV\)，不是 \(IIII\)；9 的最佳写法是 \(IX\)，不是 \(VIIII\)；8 的最佳写法是 \(VIII\)。由于不同十进制位之间互不干扰，所以只要每一位都取最短块，整个罗马数字就已经是全局最短。
降序表 \(\mathcal{T}\) 正是这一位值分解的程序化实现。先删去所有千位后，余数必然小于 1000，于是接下来决定百位，再决定十位，最后决定个位。
考虑非最小写法 \(MDCCCCLXXXXVIIII\)。它的数值为
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
把 \(1999\) 按十进制位拆开：
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
因此对应的最小块分别是
$$M,\qquad CM,\qquad XC,\qquad IX,$$
所以规范写法是 \(MCMXCIX\)。原字符串长度为 \(16\)，最小字符串长度为 \(7\)，这一行节省的字符数就是
$$16-7=9.$$
\(VIIII\to IX\) 和 \(LXXXX\to XC\) 只是同一规则在更小范围内的例子。
当 \(R(n)\) 由最小重建规则确定以后，最终答案不过是
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
每一行都可以独立处理，行与行之间没有任何全局耦合。题目的全部数学内容，都包含在“正确求值”和“最短重写”这两个局部步骤里。
C++、Python 和 Java 实现都会先把每个罗马字符映射到对应整数。随后从左到右扫描字符串，并向前看一步：如果下一个符号更大，就把当前值减掉；否则就加上去。这样就能在线性时间内得到 \(\operatorname{val}(s)\)。
得到整数后，实现按从 1000 到 1 的顺序遍历固定表 \(\mathcal{T}\)。对每个条目，只要当前余数还允许，就不断附加相应的罗马令牌，然后再转向下一个更小的条目。由于 \(CM, CD, XC, XL, IX,\) 和 \(IV\) 已经包含在表中，所以生成结果本身就是最小罗马数字。
对每一行输入，程序比较原始写法长度与重建后的最小写法长度，并把差值加入累加器。三个语言版本只有语法外观不同，算法结构完全一致。
设输入包含 \(s_1,\dots,s_N\) 这些罗马数字，总字符数为 \(L_{\text{tot}}=\sum |s_i|\)。那么求值阶段的代价是 \(O(L_{\text{tot}})\)，因为每个输入字符只检查一次。重建阶段同样与生成的最小字符串总长度线性相关，而令牌表的大小固定为 13。
在本题中，罗马数字都很短，所以常数因子非常小。从渐近意义上看，整个算法就是对输入文本总长度的线性处理，额外空间除了当前行与正在构造的最小字符串之外，只需要 \(O(1)\)。
Во входном файле записаны 1000 римских чисел. Каждая строка корректна, но не обязательно минимальна по длине. Нужно переписать каждое число в канонической кратчайшей форме и сложить общее число сэкономленных символов.
Если \(s\) обозначает римскую запись, пусть \(\operatorname{val}(s)\) будет ее числовым значением, а \(R(n)\) — минимальной римской записью числа \(n\). Тогда искомая сумма равна
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Следовательно, вся задача сводится к двум точным операциям над одной строкой: правильно вычислить ее значение и затем снова записать то же число в минимальной форме.
Римский алфавит — это \(\{M,D,C,L,X,V,I\}\) со значениями \(1000,500,100,50,10,5,1\). В минимальной записи также используются шесть вычитающих пар: \(IV, IX, XL, XC, CD,\) и \(CM\). Все вычисления в реализациях опираются именно на эти локальные правила и на десятичную блочную структуру римской записи.
Запишем строку как \(s=s_1s_2\cdots s_m\), а через \(v(s_i)\) обозначим значение \(i\)-го символа. В корректном римском числе символ дает отрицательный вклад тогда и только тогда, когда он является меньшим элементом вычитающей пары; во всех остальных случаях вклад положителен. Отсюда получается формула
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ и } v(s_i)<v(s_{i+1}),\\ 1,& \text{иначе}. \end{cases}$$
Именно поэтому разбору достаточно смотреть на один символ вперед. Если следующее значение больше, текущий символ вычитается; если нет, он прибавляется. Например,
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
Чтобы восстановить число в кратчайшей форме, реализации используют убывающий список
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
Начиная с целого числа \(n\), алгоритм каждый раз берет наибольший токен, не превосходящий текущий остаток, дописывает его римскую запись и вычитает соответствующее значение. Поскольку вычитающие формы уже включены в таблицу, результат строится сразу в каноническом виде.
Главный структурный факт состоит в том, что римская запись естественно раскладывается по десятичным разрядам. Если
$$n=1000a+100b+10c+d,$$
то минимальная римская запись получается как конкатенация блока тысяч, блока сотен, блока десятков и блока единиц.
Для разряда с символами \((u,f,t)\), обозначающими один, пять и десять раз этот разряд, минимальные блоки цифр задаются соотношением
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
Поэтому разряд единиц использует \((I,V,X)\), разряд десятков — \((X,L,C)\), разряд сотен — \((C,D,M)\). Блок тысяч — это просто \(a\) подряд идущих символов \(M\).
Для каждой цифры более короткого допустимого блока не существует. Число 4 оптимально записывать как \(IV\), а не \(IIII\); число 9 — как \(IX\), а не \(VIIII\); число 8 — как \(VIII\). Так как разные разряды не мешают друг другу, минимизация каждого блока по отдельности дает глобально минимальную запись всего числа.
Убывающая таблица \(\mathcal{T}\) является точной алгоритмической формой этой разрядной декомпозиции. После удаления всех тысяч остаток становится меньше 1000, затем фиксируются сотни, потом десятки и в конце единицы.
Рассмотрим неминимальную запись \(MDCCCCLXXXXVIIII\). Ее значение равно
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
Разложим \(1999\) по разрядам:
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
Тогда минимальные блоки таковы:
$$M,\qquad CM,\qquad XC,\qquad IX,$$
поэтому каноническая форма — \(MCMXCIX\). Исходная строка имеет длину \(16\), минимальная строка — длину \(7\), а значит, эта одна строка экономит
$$16-7=9$$
символов. Упрощения \(VIIII\to IX\) и \(LXXXX\to XC\) являются лишь меньшими примерами той же самой схемы.
Как только \(R(n)\) определено правилом минимальной реконструкции, окончательный ответ имеет вид
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
Каждая строка обрабатывается независимо. Никакой глобальной комбинаторики здесь нет; вся математика заключена в правильной интерпретации и минимальной перезаписи одного римского числа.
Реализации на C++, Python и Java сначала сопоставляют каждому римскому символу его целочисленное значение. Затем строка просматривается слева направо с просмотром на один символ вперед: если следующий символ больше, текущее значение вычитается, иначе прибавляется. Так за один проход вычисляется \(\operatorname{val}(s)\).
После получения целого числа реализация проходит по фиксированной таблице \(\mathcal{T}\) от 1000 к 1. Для каждого элемента соответствующий токен добавляется столько раз, сколько возможно, после чего алгоритм переходит к следующему меньшему значению. Поскольку \(CM, CD, XC, XL, IX,\) и \(IV\) уже присутствуют в таблице, построенная строка сразу является минимальным римским числом.
Для каждой входной строки программа сравнивает длину исходной записи с длиной восстановленной минимальной записи и прибавляет разность к накопленной сумме. Все три языковые версии различаются только синтаксисом, а не алгоритмом.
Если вход состоит из чисел \(s_1,\dots,s_N\) общей длины \(L_{\text{tot}}=\sum |s_i|\), то разбор занимает \(O(L_{\text{tot}})\), поскольку каждый входной символ просматривается один раз. Реконструкция также линейна по длине построенных минимальных строк, а размер таблицы токенов фиксирован и равен 13.
В этой задаче римские числа короткие, поэтому постоянные множители малы. Асимптотически весь алгоритм линеен по общему объему входного текста, а дополнительная память равна \(O(1)\) сверх текущей строки и строящейся минимальной записи.
يحتوي ملف الإدخال على 1000 عدد روماني. كل سطر صحيح من حيث القواعد، لكنه ليس بالضرورة مكتوبًا بأقصر صيغة ممكنة. المطلوب هو إعادة كتابة كل سطر بالصيغة الرومانية الدنيا القياسية لنفس العدد الصحيح، ثم جمع عدد الأحرف التي تم توفيرها.
إذا رمزنا إلى أحد السطور بـ \(s\)، ولتكن \(\operatorname{val}(s)\) قيمته الصحيحة، ولتكن \(R(n)\) الصيغة الرومانية الدنيا للعدد \(n\)، فإن الكمية المطلوبة هي
$$\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
وهكذا تختزل المسألة كلها إلى عمليتين محددتين على سلسلة رومانية واحدة: حساب قيمتها بشكل صحيح، ثم إعادة بنائها في الصورة الدنيا.
الأبجدية الرومانية هي \(\{M,D,C,L,X,V,I\}\)، وقيمها هي \(1000,500,100,50,10,5,1\) على الترتيب. وتستخدم الصيغة الدنيا أيضًا الأزواج الطرحية الستة \(IV, IX, XL, XC, CD,\) و\(CM\). جميع الأفكار التي تعتمد عليها الحلول تأتي من هذه القواعد المحلية ومن البنية العشرية لكتابة الأعداد الرومانية.
لنكتب السلسلة الرومانية على الصورة \(s=s_1s_2\cdots s_m\)، ولتكن \(v(s_i)\) قيمة الرمز رقم \(i\). في عدد روماني صحيح، يكون الرمز ذا مساهمة سالبة بالضبط عندما يكون هو الأصغر داخل زوج طرحي؛ وفي غير ذلك تكون مساهمته موجبة. ومن ثم نحصل على الصيغة
$$\operatorname{val}(s)=\sum_{i=1}^{m}\sigma_i\,v(s_i),\qquad \sigma_i= \begin{cases} -1,& i<m \text{ and } v(s_i)<v(s_{i+1}),\\ 1,& \text{otherwise}. \end{cases}$$
ولهذا السبب لا يحتاج التحليل إلا إلى النظر خطوة واحدة إلى الأمام. فإذا جاءت قيمة أكبر بعد الرمز الحالي حصل الطرح، وإذا لم ترتفع القيمة حصل الجمع. وعلى سبيل المثال
$$MCMXCIX=1000-100+1000-10+100-1+10=1999.$$
لإعادة بناء العدد بأقصر صورة، تستخدم الحلول الجدول التنازلي
$$\mathcal{T}=\bigl[(1000,M),(900,CM),(500,D),(400,CD),(100,C),(90,XC),(50,L),(40,XL),(10,X),(9,IX),(5,V),(4,IV),(1,I)\bigr].$$
ننطلق من عدد صحيح \(n\)، ثم نختار في كل مرة أكبر رمز لا تتجاوز قيمته الباقي الحالي، ونلحق كتابته الرومانية، ثم نطرح قيمته. وبما أن الجدول يحتوي أصلًا على الصور الطرحية، فإن الناتج يتكون مباشرة بصيغة رومانية دنيا وقياسية.
الحقيقة البنيوية الأساسية هي أن الأعداد الرومانية تنفصل طبيعيًا بحسب المنازل العشرية. فإذا كان
$$n=1000a+100b+10c+d,$$
فإن الصيغة الرومانية الدنيا تتكون من وصل كتلة الآلاف ثم كتلة المئات ثم كتلة العشرات ثم كتلة الآحاد.
وبالنسبة إلى منزلة رموزها \((u,f,t)\)، أي رمز الواحد والخمسة والعشرة لتلك المنزلة، فإن الكتل الدنيا للأرقام تحقق
$$\bigl(\phi_{u,f,t}(0),\phi_{u,f,t}(1),\dots,\phi_{u,f,t}(9)\bigr)=\bigl(\varepsilon,u,uu,uuu,uf,f,fu,fuu,fuuu,ut\bigr).$$
وبذلك تستعمل منزلة الآحاد \((I,V,X)\)، وتستعمل منزلة العشرات \((X,L,C)\)، وتستعمل منزلة المئات \((C,D,M)\). أما كتلة الآلاف فهي ببساطة \(a\) نسخ متتالية من \(M\).
ولا توجد لأي رقم كتلة صحيحة أقصر من هذه. فالعدد 4 يكتب على أفضل وجه \(IV\) لا \(IIII\)، والعدد 9 يكتب \(IX\) لا \(VIIII\)، والعدد 8 يكتب \(VIII\). وبما أن المنازل المختلفة لا تتداخل فيما بينها، فإن تصغير كل كتلة على حدة يكفي للحصول على أصغر كتابة ممكنة للعدد كله.
والجدول التنازلي \(\mathcal{T}\) ليس إلا الصياغة الإجرائية لهذا التحليل بالمنازل. فبعد إزالة جميع الآلاف يصبح الباقي أقل من 1000، ثم تتحدد المئات، ثم العشرات، ثم الآحاد.
لنأخذ الكتابة غير الدنيا \(MDCCCCLXXXXVIIII\). قيمتها العددية هي
$$1000+(500+4\cdot100)+(50+4\cdot10)+(5+4\cdot1)=1999.$$
والآن نفكك \(1999\) بحسب المنازل:
$$1999=1\cdot1000+9\cdot100+9\cdot10+9.$$
إذن الكتل الدنيا هي
$$M,\qquad CM,\qquad XC,\qquad IX,$$
فتكون الصيغة القياسية \(MCMXCIX\). طول السلسلة الأصلية هو \(16\)، وطول السلسلة الدنيا هو \(7\)، ولذلك فإن هذا السطر الواحد يوفر
$$16-7=9$$
أحرف. والتحويلان \(VIIII\to IX\) و\(LXXXX\to XC\) مجرد حالتين أصغر من القاعدة نفسها.
بعد تعريف \(R(n)\) بقاعدة إعادة البناء الدنيا، تصبح الإجابة النهائية مجرد
$$\text{saved}=\sum_s \bigl(|s|-|R(\operatorname{val}(s))|\bigr).$$
كل سطر يعالج مستقلًا عن بقية السطور. لا توجد هنا بنية تركيبية عالمية مخفية؛ فكل الرياضيات اللازمة موجودة في التقييم الصحيح وإعادة الكتابة الدنيا لسلسلة رومانية واحدة.
تبدأ تطبيقات C++ وPython وJava بربط كل حرف روماني بقيمته الصحيحة. ثم تمسح السلسلة من اليسار إلى اليمين مع نظرة واحدة إلى الرمز التالي: إذا كان الرمز التالي أكبر، تُطرح القيمة الحالية؛ وإلا تُضاف. وهكذا تُحسب \(\operatorname{val}(s)\) في مرور واحد.
بعد الحصول على القيمة الصحيحة، تمر الشيفرة على الجدول الثابت \(\mathcal{T}\) من 1000 نزولًا إلى 1. ولكل عنصر تضيف الرمز الروماني الموافق ما دام ذلك ممكنًا، ثم تنتقل إلى القيمة الأصغر التالية. وبما أن \(CM, CD, XC, XL, IX,\) و\(IV\) موجودة أصلًا في الجدول، فإن السلسلة الناتجة هي بالفعل الصيغة الرومانية الدنيا نفسها.
في كل سطر من الإدخال، تقارن الشيفرة بين طول الكتابة الأصلية وطول الكتابة الدنيا المعاد بناؤها، ثم تضيف الفرق إلى مجموع جارٍ. الفروق بين النسخ الثلاث سطحية في الصياغة فقط، أما الإجراء الحسابي فهو واحد.
إذا احتوى الإدخال على الأعداد \(s_1,\dots,s_N\) وكان مجموع أطوالها \(L_{\text{tot}}=\sum |s_i|\)، فإن مرحلة التحليل تكلف \(O(L_{\text{tot}})\)، لأن كل حرف من الإدخال يفحص مرة واحدة. كما أن مرحلة إعادة البناء خطية في طول السلاسل الدنيا الناتجة، بينما حجم جدول الرموز ثابت ويساوي 13.
في هذه المسألة تكون الأعداد الرومانية قصيرة، لذلك تكون الثوابت صغيرة جدًا. ومن منظور تقاربي، فالحساب كله خطي في حجم النص الداخل، ويستهلك \(O(1)\) من الذاكرة الإضافية خارج السطر الحالي والسلسلة الدنيا التي يجري بناؤها.