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

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

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

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

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