24. Подсчет символов: #297638
Текстовый файл состоит из десятичных цифр и знаков арифметических операций «$-$» и «$*$» (вычитания и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными $6$-ричными числами, в котором порядок действий слева направо совпадает с порядком действий по правилам математики. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули.
В ответе укажите количество символов.
Первое: числа шестиричные. Значит допустимы только цифры от $0$ до $5$, а цифры $6$, $7$, $8$, $9$ становятся такими же разделителями, как и знаки операций. Разница лишь в том, что через знак операции выражение можно продолжить влево, а через цифру $7$ — нельзя.
Второе, главное: порядок действий слева направо должен совпадать с математическим. Умножение приоритетнее вычитания, поэтому расхождение возникает ровно тогда, когда после какого-то вычитания дальше встречается умножение. Математика выполнила бы это умножение раньше, а чтение слева направо — позже. Значит корректная запись имеет жёсткую форму: сначала идут все умножения, потом все вычитания. Схематично это число, затем группа $*$-звеньев, затем группа $-$-звеньев.
Отсюда динамика на два состояния. Для каждой позиции $j$, где кончается число, считаем $M[j]$ — длину самого длинного выражения, в котором пока встречались только умножения, и $S[j]$ — длину самого длинного выражения, где вычитания уже начались. Переход через $*$ разрешён только из состояния $M$ в $M$, переход через $-$ — из любого состояния в $S$. Обратной дороги нет: попав в $S$, умножение уже не приписать.
Число — либо одиночный $0$, либо цифра из $1$–$5$, за которой идут цифры $0$–$5$. Фрагмент может начаться в середине цепочки цифр, отбросив ведущие нули, но тогда продолжить его влево знаком операции нельзя, слева стоит цифра. Это отражает переменная chain.
s = open('24-28.txt').read().strip()
n = len(s)
dig = set('012345') # цифры 6-ричной системы
M = [0] * n # выражение только с умножениями
S = [0] * n # выражение, где уже начались вычитания
best = 0
r = 0 # начало текущей цепочки 6-ричных цифр
for j in range(n):
if s[j] not in dig: # знак операции или цифра 6..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) # 51
Проверка найденного фрагмента: это $3021!!1!!1!!1!!1!!2!!3!!3!!4!!2!-!25430!-!451!-!12!-!12!-!4431!-!0!-!0!-!0!-!1$, длина $51$. Хорошо видна требуемая структура: сначала блок умножений, потом блок вычитаний. Слева от фрагмента стоит цифра $4$, справа после последней единицы идёт $-$, два знака подряд.