Задача #4258

Работа со строками

Сложнее ЕГЭ

Текстовый файл состоит из заглавных букв латинского алфавита - цифр римской системы счисления I, V, X, L, C, D, M.
Определите в прилагаемом файле максимальное количество идущих подряд символов, которые представляют собой корректную римскую запись десятичного числа. Если найдено несколько таких последовательностей, выберите ту которая обозначает наименьшее десятичное число. В ответе укажите десятичное число, соответствующее найденной последовательности римских цифр.
Для выполнения этого задания следует написать программу.
Примечание.
В римской системе счисления приняты следующие правила:
1) в качестве цифр используют заглавные латинские буквы I, V, X, L, C, D, M, числовое значение которых 1, 5, 10, 50, 100, 500 и 1000 соответственно;
2) цифры V, L, D никогда не повторяются;
3) цифры I, X, C, M могут повторяться не более трёх раз подряд;
4) если меньшая цифра стоит слева от большей, её значение вычитается из большей; вычитать можно только одну цифру I, Х или С; вычитаемое не может быть меньше одной десятой от уменьшаемого;
5) если цифра стоит справа от большей или равной, их значения складываются;
6) цифры в записи числа располагаются слева направо в порядке невозрастания их числового значения за исключением случаев вычитания.
Например, римская запись MMXXVI корректна обозначает число 2026, а запись MDDIVXXX некорректна.

Файлы к задаче

Скачать 24.txt

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

2388

Видео по задаче

Смотреть в VK

I способ. Перевод десятичных чисел в римские и подбор

def rim(n):
    s = ''
    dig = [(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')]
    for d,r in dig:
        while n>=d:
            s+=r
            n-=d
    return s

#m = 0
for i in range(1,4000):
    if rim(i) in s:
        if len(rim(i))==13:
            print(i, rim(i))
        #m = max(m,len(rim[i]))
#print(m)

II способ. Регулярные выражения + перевод римских в десятичные (автор: Артур Грицких)

from re import finditer
def to_dec(r):
  dct = {
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000
  }
  d = dct[r[-1]]
  for i in range(len(r) - 2, -1, -1):
    if dct[r[i]] >= dct[r[i + 1]]:
      d += dct[r[i]]
    else:
      d -= dct[r[i]]
  return d
s = open('24.txt').read()
reg = r'M{,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})'
a = [ (len(x.group()), x.group()) for x in finditer(reg, s) if x.group()]
a.sort(key=lambda x: (-x[0], to_dec(x[1])))
print(a[0][1], to_dec(a[0][1]))

Номер