Что спрашивают
Строка содержит заглавные буквы и цифры. Числом считается весь непрерывный блок цифр между буквами или границами строки. Найдите наибольшее чётное число и выведите его без ведущих нулей.
Выбирать часть блока нельзя. Нули в начале допустимы, число 0 чётное. Каждый блок содержит не больше восемнадцати цифр; хотя бы одно чётное число существует.
Приём решения
Идём слева направо, накапливая значение текущего числового блока. Для очередной цифры обновление равно value = value * 10 + digit. Оно естественно убирает влияние ведущих нулей.
Проверяем чётность и максимум только после завершения всего блока — при встрече буквы. Нечётный блок отбрасывается целиком, даже если какой-то его префикс был чётным.
- Храните значение блока и признак, что сейчас прочитана хотя бы одна цифра.
- На цифре дописывайте её к значению.
- На букве завершайте блок: проверяйте
value % 2 == 0, обновляйте максимум и сбрасывайте состояние. - Обработайте также блок, который заканчивается вместе со строкой.
Чтобы хвост обрабатывался тем же правилом, код использует chain(s, 'A'): после входных символов приходит ещё одна буква-разделитель. В отличие от создания s + 'A', итератор не копирует всю строку.
Сравниваются целые значения, а не строки и не float: строковый порядок зависит от длины и ведущих нулей, а float может потерять точность длинного целого. Время — O(n), дополнительное состояние — O(1), поскольку длина числа ограничена.
Разбор на примере
Ввод
A0008B8647C120D0300
Вывод
300
| Полный блок | Значение | Проверка | Лучшее |
|---|---|---|---|
| 0008 | 8 | Чётное | 8 |
| 8647 | 8647 | Нечётное: весь блок исключён | 8 |
| 120 | 120 | Чётное | 120 |
| 0300 | 300 | Хвост строки, чётное | 300 |
Блок 0008 означает число 8. Блок 8647 нечётный; брать из него 864 нельзя. Затем получаем 120 и в самом конце 0300, то есть 300. Дополнительная буква завершает последний блок, и наибольшее чётное значение выводится как 300.
Код на Python и C++
Кандидат проверяется только на границе блока. Инициализация best нулём допустима: числа неотрицательные, а условие гарантирует наличие чётного.
В C++ вместо chain(s, 'A') перебирается строка s + 'A'. Число до 18 цифр помещается в long long (до 9,2·1018). Если бы цифр могло быть больше, записи пришлось бы сравнивать как строки без ведущих нулей: сначала по длине, при равной длине посимвольно.
import sys
from itertools import chain
def solve(s):
best = value = 0
in_number = False
for ch in chain(s, 'A'):
if '0' <= ch <= '9':
value = value * 10 + int(ch)
in_number = True
elif in_number:
if value % 2 == 0:
best = max(best, value)
value = 0
in_number = False
return best
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<algorithm>
<iostream>
<string>
using namespace std;
long long solve(const string& s) {
long long best = 0, value = 0;
bool in_number = false;
for (char ch : s + 'A') {
if ('0' <= ch && ch <= '9') {
value = value * 10 + (ch - '0');
in_number = true;
} else if (in_number) {
if (value % 2 == 0)
best = max(best, value);
value = 0;
in_number = false;
}
}
return best;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Взять чётный префикс нечётного блока
Числом считается весь максимальный блок цифр. Проверка промежуточного значения до границы нарушает это правило.
- Сравнивать числовые блоки как строки
Строка 98 может лексикографически идти после 120, хотя её значение меньше. Ведущие нули добавляют ещё одно различие.
- Пропустить последний блок
Если строка заканчивается цифрой, обычной буквы-разделителя после неё нет. Нужна явная обработка хвоста или дополнительный символ в итераторе.
- Преобразовать длинное число в float
Для точного сравнения используйте целые числа. Двоичная вещественная запись не сохраняет все длинные целые значения точно.