24. Подсчет символов: #297636
Текстовый файл состоит из десятичных цифр и знаков арифметических операций «$-$» и «$*$» (вычитания и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением c целыми неотрицательными $8$-ричными числами, в котором порядок действий слева направо совпадает с порядком действий по правилам математики. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули.
В ответе укажите количество символов.
Сначала о самом файле. В нём пять строк: первые три — текст условия, и только четвёртая содержит данные, ровно $10$ миллионов символов. Читать файл целиком нельзя, иначе цифры из фразы про $8$-ричные числа попадут в обработку. Берём именно строку с данными.
Числа восьмеричные, значит допустимы только цифры от $0$ до $7$, а цифры $8$ и $9$ становятся разделителями наравне со знаками операций. Разница между ними одна: через знак операции выражение продолжается влево, а через цифру $9$ — нет.
Порядок действий слева направо должен совпадать с математическим. Умножение приоритетнее вычитания, поэтому расхождение возникает ровно тогда, когда после какого-то вычитания дальше встречается умножение: математика выполнила бы его раньше, а чтение слева направо — позже. Значит корректная запись имеет жёсткую форму: сначала все умножения, потом все вычитания.
Отсюда динамика на два состояния. Для каждой позиции $j$, где кончается число, считаем $M[j]$ — длину самого длинного выражения, где пока были только умножения, и $S[j]$ — длину самого длинного выражения, где вычитания уже начались. Переход через $*$ возможен только из $M$ в $M$, переход через $-$ — из любого состояния в $S$. Обратной дороги нет: попав в $S$, умножение уже не приписать.
Число — либо одиночный $0$, либо цифра из $1$–$7$, за которой идут цифры $0$–$7$. Фрагмент может начаться в середине цепочки цифр, отбросив ведущие нули, но тогда влево его знаком операции не продолжить, слева стоит цифра. Это отражает переменная chain.
s = open('24-29.txt', encoding='utf-8').read().split('\n')[3] # строка с данными
n = len(s)
dig = set('01234567') # цифры 8-ричной системы
M = [0] * n # выражение только с умножениями
S = [0] * n # выражение, где уже начались вычитания
best = 0
r = 0 # начало текущей цепочки 8-ричных цифр
for j in range(n):
if s[j] not in dig: # знак операции или цифра 8, 9 — обрыв цепочки
r = j + 1
continue
# число, кончающееся в позиции j
if s[r] != '0':
num_len = j - r + 1
chain = r
elif j == r: # само число 0
num_len = 1
chain = r
else: # цепочка началась с 0 — стартуем с первой ненулевой
q = r
while q <= j and s[q] == '0':
q += 1
num_len = j - q + 1 if q <= j else 1
chain = -1 # слева цифра, знак операции не приписать
m, sm = num_len, 0 # одно число — уже верное выражение
if chain >= 2 and s[chain-2] in dig:
prev = s[chain-1]
if prev == '*' and M[chain-2] > 0: # умножение только после умножений
m = max(m, M[chain-2] + 1 + num_len)
if prev == '-': # вычитание можно после любого
base = max(M[chain-2], S[chain-2])
if base > 0:
sm = base + 1 + num_len
M[j], S[j] = m, sm
best = max(best, m, sm)
print(best) # 71
Проверка найденного фрагмента: это $61246!!25450!!0!!0!!0!!0!!0!!0!!0!!0!!163!!465!!2600!-!354324063!-!565!-!566!-!6!-!0!-!0!-!0!-!2600$, длина $71$. Требуемая структура видна сразу: блок умножений, затем блок вычитаний. Слева стоит цифра $3$, справа после последнего $2600$ идёт $*$, а умножение после вычитаний уже невозможно.