24. Подсчет символов: Текстовый файл состоит из цифр 0, 6, 7, 8, 9 и знаков арифметических операций…
Текстовый файл состоит из цифр $0$, $6$, $7$, $8$, $9$ и знаков арифметических операций «$-$» и «$*$» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число $0$ не имеет знака.
В ответе укажите количество символов.
Сначала формализуем, что такое корректное выражение. Это число, за которым идёт любое количество пар «знак операции плюс число». Число — это либо одиночный $0$, либо цифра из $6$–$9$, за которой идут любые цифры набора $0$, $6$, $7$, $8$, $9$. Условие про ведущие нули означает ровно одно: с нуля может начинаться только само число $0$.
Ключевой момент, на котором чаще всего ошибаются: искомый фрагмент — это подстрока, поэтому он имеет право начаться в середине блока цифр. Например, в куске $00789$ подстрока $789$ — корректное число. Но такой «обрезанный» старт нельзя продолжить влево знаком операции, потому что слева от него стоит цифра. Значит присоединять к выражению что-то слева можно только тогда, когда число начинается с самого начала своего блока цифр.
Решаем динамикой. Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, заканчивающегося в этой позиции. Есть два варианта: либо выражение состоит из одного числа, либо к числу слева через знак операции приклеивается уже посчитанное выражение, которое кончалось на два символа левее начала числа.
s = open('24-08.txt').read().strip()
n = len(s)
ops = set('-*')
L = [0] * n # L[j] — длина макс. верного выражения, кончающегося в j
best = 0
r = 0 # начало текущего блока цифр
for j in range(n):
if s[j] in ops:
r = j + 1
continue
# 1) выражение из одного числа
if s[r] != '0': # блок начинается со значащей цифры
cur = j - r + 1
chain_start = r
elif j == r: # само число 0
cur = 1
chain_start = r
else: # блок начался с 0 — стартуем с первой ненулевой
q = r
while q <= j and s[q] == '0':
q += 1
cur = j - q + 1 if q <= j else 1
chain_start = -1 # слева цифра, знак операции не приписать
# 2) приклеиваем слева выражение через знак операции
if chain_start >= 2 and s[chain_start-1] in ops and L[chain_start-2] > 0:
cur = max(cur, L[chain_start-2] + 1 + (j - chain_start + 1))
L[j] = cur
best = max(best, cur)
print(best) # 154
Проверка найденного фрагмента: длина $154$, он целиком распознаётся регулярным выражением для корректной записи, а слева и справа от него стоят знаки $*$, то есть расширить его нельзя.