Что спрашивают
Дана строка из заглавных латинских букв и цифр 1–9. Найдите максимальную длину фрагмента, являющегося записью числа в двенадцатеричной системе. Для значений десять и одиннадцать используются A и B.
В двенадцатеричной системе допустимы цифры 0–9, A, B. В этом конкретном входе нулей нет, поэтому вопросы ведущих нулей не возникают. В ответе нужна длина, а не значение числа.
Приём решения
Если каждый символ фрагмента является допустимой цифрой, весь фрагмент образует запись числа. Значит, снова ищем самую длинную серию разрешённых символов. Для основания двенадцать разрешённый набор — 0123456789AB; остальные буквы разрывают серию.
- Задайте набор допустимых цифр.
- Увеличивайте текущую длину на разрешённом символе.
- Обнуляйте её на любой другой букве.
- Запоминайте максимальную длину после каждого символа.
Переводить фрагменты в десятичную систему не требуется. Такая операция вычисляла бы величину, о которой не спрашивают, и усложняла работу с длинными числами. Здесь достаточно проверить принадлежность каждого символа алфавиту.
Для другого основания сначала выпишите допустимые цифры по его правилам. Нельзя автоматически разрешать буквы A–F только потому, что они известны по шестнадцатеричной записи. Для текущей задачи каждая проверка выполняется за постоянное время, весь проход — O(n), состояние — O(1).
Разбор на примере
Ввод
C9ABDD12AB7Z
Вывод
5
| Участок | Допустим в основании 12 | Длина серии |
|---|---|---|
| C | Нет | 0 |
| 9AB | Да | 3 |
| DD | Нет: сброс | 0 |
| 12AB7 | Да | 5 |
| Z | Нет | 0 |
Буквы C и D не являются цифрами двенадцатеричной системы, поэтому объединять фрагменты через них нельзя. Подходящие серии — 9AB и 12AB7. Вторая длиннее, её длина — пять. Буквы A и B считаются обычными цифрами и не разрывают запись.
Код на Python и C++
Набор содержит математически допустимый ноль, хотя по условиям задачи он во входе не встречается. Результат — число символов подходящей серии.
В C++ принадлежность символа набору проверяет allowed.find(ch) != string::npos.
import sys
def solve(s):
allowed = '0123456789AB'
current = best = 0
for ch in s:
current = current + 1 if ch in allowed else 0
best = max(best, current)
return best
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<algorithm>
<iostream>
<string>
using namespace std;
int solve(const string& s) {
const string allowed = "0123456789AB";
int current = 0, best = 0;
for (char ch : s) {
current = allowed.find(ch) != string::npos ? current + 1 : 0;
best = max(best, current);
}
return best;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Разрешить все шестнадцатеричные цифры
В основании двенадцать C, D, E и F уже недопустимы. Старшая цифра здесь B.
- Разрешить только десятичные цифры
Буквы A и B тоже входят в число. Проверка только isdigit потеряет допустимые участки.
- Искать наибольшее значение числа
Требуется максимальная длина записи. Сравнивать или переводить сами числовые значения не нужно.