Подготовка к школе
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
Для всех
Назад

24. Подсчет символов: #297636

Сообщить о проблеме
Задание #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$ идёт $*$, а умножение после вычитаний уже невозможно.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение