Roma rəqəmləri#2900
Verilmiş sətir 'I', 'V', 'X', 'L', 'C', 'D' və 'M' simvollarından ibarətdir. Siz bu sətri bir neçə hissəyə bölməlisiniz ki, hər bir hissə düzgün Roma rəqəmi təşkil etsin və bu rəqəmlərin cəmi mümkün qədər kiçik olsun.
Düzgün Roma rəqəmi aşağıdakı qaydada qurulur. Əvvəlcə 'M' simvolu ədədin minliklərinin sayına uyğun olaraq yazılır. Məsələn, 2045 ədədində iki minlik var, ona görə də bu rəqəmin Roma şəklində yazılışı "MM" ilə başlayır. Daha sonra, 1000-ə qalıq tapılır. Bu qalqda olan yüzlüklərin sayına əsasən aşağıdakılardan biri əlavə olunur: bir yüzlük üçün "C", iki yüzlük üçün "CC", üç yüzlük üçün "CCC", daha sonra "CD", "D", "DC", "DCC", "DCCC" və ya üçdən doqquza qədər yüzlüklər üçün "CM" əlavə olunur. 2045 üçün qalıq 45-dir, bu da yüzlük olmadığını göstərir, ona görə də heç nə əlavə olunmur.
Sonra, 100-ə qalıq tapılır. Qalıqda olan onluqların sayına əsasən "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" (əgər onluq yoxdursa, heç nə əlavə olunmur) əlavə olunur. 2045 üçün "XL" əlavə olunur.
Daha sonra, ilkin ədəd 10-a bölünərkən alınan qalıqda olan vahidlərə əsasən "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" (uyğun olaraq 1, 2, ..., 9 üçün) əlavə olunur. Əgər qalığ sıfırdırsa, heç nə əlavə olunmur. 2045 üçün isə "V" əlavə olunur.
Beləliklə, 2045 ədədinin Roma rəqəmi "MMXLV" olacaq.
Əlavə olaraq, məhdudiyyət var: Roma rəqəmlərində heç bir simvol ard-arda dörddən artıq təkrarlana bilməz. Odur ki, yalnız 1-dən 3999-a qədər olan ədədlər üçün düzgün Roma rəqəmi mövcuddur.
Girişdə 'I', 'V', 'X', 'L', 'C', 'D' və 'M' böyük latın hərflərindən ibarət, uzunluğu ən çox 20000 olan bir ədəd, boş olmayan sətir verilir.
Çıxışa bu rəqəmlərin mümkün olan ən kiçik cəmini verin.
Nümunə 1