0У
Все задачи №24
№24

Корректная римская запись

Текстовый файл. Файл из римских цифр I V X L C D M. Найди максимальную по длине подпоследовательность, которая является корректной римской записью десятичного числа; если таких несколько, выбери ту, что обозначает наименьшее число. В ответе — это число.

Источник: ФИПИ, № 31160

Скачать файл: task_31160_A.txt. В редакторе он уже лежит рядом с кодом, открывай как на экзамене: open('task_31160_A.txt').

Ответвпиши то, что вывела программа
Показать разбор
  1. Опиши корректное римское число регуляркой по разрядам: тысячи, сотни, десятки, единицы. В каждом разряде свои варианты, например CM, CD или D с тремя C.
  2. Совпадения могут перекрываться, поэтому ищи через заглядывание вперёд (?=...): так проверится каждая стартовая позиция.
  3. Найди наибольшую длину и собери все записи такой длины.
  4. Переведи их в десятичные числа и выведи наименьшее.
from re import finditer
s = open('task_31160_A.txt').readline().strip()
r = r'(?=(M{0,3}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})))'
mx = 0
best = set()
for x in finditer(r, s):
    c = x.group(1)
    if len(c) > mx:
        mx = len(c)
        best = {c}
    elif len(c) == mx:
        best.add(c)

def value(c):
    d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    t = 0
    for i in range(len(c)):
        if i + 1 < len(c) and d[c[i]] < d[c[i + 1]]:
            t -= d[c[i]]
        else:
            t += d[c[i]]
    return t

print(min(value(c) for c in best))