Что спрашивают
В строке из I, V, X, L, C, D, M нужно найти самый длинный фрагмент, являющийся канонической римской записью числа от 1 до 3999. При равной длине выбирается меньшее числовое значение. Выводится десятичное число.
Нельзя просто складывать и вычитать значения всей строки: сначала нужно убедиться, что выбранный фрагмент составлен по разрешённым формам тысяч, сотен, десятков и единиц.
Приём решения
Каноническая запись состоит из четырёх последовательных блоков. Каждый блок может быть пустым, но вся запись — нет. Для тысяч разрешено до трёх M. Для остальных разрядов есть две вычитательные пары либо старшая цифра разряда с несколькими младшими.
| Разряд | Регулярное выражение |
|---|---|
| Тысячи | M{0,3} |
| Сотни | CM|CD|D?C{0,3} |
| Десятки | XC|XL|L?X{0,3} |
| Единицы | IX|IV|V?I{0,3} |
Соединим блоки в одну регулярную форму. Проверять её нужно с каждого начала, включая начала внутри уже найденного фрагмента. Для этого используем опережающую проверку (?=(...)): совпадение не поглощает символы, а найденная запись доступна в первой группе.
- Получите наиболее длинный допустимый префикс с каждого начала: блоки выражения выбирают свои максимальные допустимые формы.
- Пропускайте пустые совпадения, возможные из-за пустых блоков.
- Переведите найденную запись в десятичное значение, вычитая символ перед более крупным и складывая остальные.
- Сравните пару
(-длина, значение)с лучшей: отрицательная длина обеспечивает максимум, значение — минимум при равенстве.
Проверка канонической формы идёт до вычисления значения. Например, формальная вычитательная трактовка IL не делает её разрешённой записью 49; канонический вариант — XLIX.
Длина разрешённой записи ограничена пятнадцатью символами: до трёх тысяч и до четырёх знаков в каждом оставшемся разряде. Поэтому работа с каждым началом ограничена постоянной величиной, итоговое время — O(n), дополнительная память — O(1). Все 3999 записей перечислять для каждого входа не требуется.
Разбор на примере
Ввод
XVIIILXIII
Вывод
18
| Начало | Длиннейшая запись отсюда | Длина | Значение |
|---|---|---|---|
| 0 | XVIII | 5 | 18 |
| 1 | VIII | 4 | 8 |
| 5 | LXIII | 5 | 63 |
В строке есть две записи длины пять: XVIII и LXIII. Они означают 18 и 63, поэтому выбирается 18. Вся строка канонической записью не является: после блока единиц XVIII нельзя приписать новый десяток. Более короткая VIII не выигрывает, хотя её значение ещё меньше.
Код на Python и C++
decimal применяется только к уже проверенным записям. Первая координата пары отрицательна: длинные фрагменты при сравнении min идут раньше коротких.
В C++ тот же шаблон через std::regex тоже работает: совпадения короткие. Но на строке в миллион символов он в несколько раз медленнее, поэтому в коде на C++ шаблон записан функцией roman_length. Она с каждой позиции проходит тысячи, сотни, десятки и единицы в том же порядке, что и шаблон. Пара (-длина, значение) — pair<int, int>.
import re
import sys
VALUES = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000}
PATTERN = (r'M{0,3}(?:CM|CD|D?C{0,3})'
r'(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})')
OVERLAP = re.compile(r'(?=(' + PATTERN + r'))')
def decimal(word):
total = 0
for i, ch in enumerate(word):
value = VALUES[ch]
if i + 1 < len(word) and value < VALUES[word[i + 1]]:
total -= value
else:
total += value
return total
def solve(s):
best = (0, 0)
for match in OVERLAP.finditer(s):
word = match.group(1)
if word:
best = min(best, (-len(word), decimal(word)))
return best[1]
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<iostream>
<map>
<string>
<utility>
using namespace std;
map<char, int> VALUES = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
{'C', 100}, {'D', 500}, {'M', 1000}};
// Длина разряда с позиции i: две буквы вычитания (CM, CD) или
// старшая буква разряда и до трёх младших (D?C{0,3}). Так же для десятков и единиц.
int digit_length(const string& s, int i, char one, char five, char ten) {
int n = s.size();
if (i + 1 < n && s[i] == one && (s[i + 1] == ten || s[i + 1] == five))
return 2;
int length = 0;
if (i < n && s[i] == five)
length = 1;
for (int k = 0; k < 3 && i + length < n && s[i + length] == one; k++)
length += 1;
return length;
}
// То же, что шаблон M{0,3}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3}) с позиции start.
int roman_length(const string& s, int start) {
int i = start, n = s.size();
for (int k = 0; k < 3 && i < n && s[i] == 'M'; k++)
i += 1;
i += digit_length(s, i, 'C', 'D', 'M');
i += digit_length(s, i, 'X', 'L', 'C');
i += digit_length(s, i, 'I', 'V', 'X');
return i - start;
}
int decimal(const string& word) {
int total = 0;
for (size_t i = 0; i < word.size(); i++) {
int value = VALUES[word[i]];
if (i + 1 < word.size() && value < VALUES[word[i + 1]])
total -= value;
else
total += value;
}
return total;
}
int solve(const string& s) {
pair<int, int> best = {0, 0};
for (int start = 0; start < (int)s.size(); start++) {
int length = roman_length(s, start);
if (length > 0)
best = min(best, {-length, decimal(s.substr(start, length))});
}
return best.second;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Посчитать значение всей строки без проверки формы
Правило вычитания само по себе не проверяет каноничность. Сначала найдите фрагмент, соответствующий формам разрядов.
- Искать только непересекающиеся совпадения
Правильная запись может начинаться внутри предыдущего совпадения и оказаться длиннее. Нужно просмотреть все начала.
- Сначала минимизировать значение
Главный критерий — длина. Меньшее число выбирается лишь среди записей одинаковой максимальной длины.
- Выбрать большее значение при равенстве
Второй элемент пары сравнивается по возрастанию. Отрицательна только длина, но не десятичное значение.