Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

24. Подсчет символов: Текстовый файл состоит из цифр 0, 5, 6, 7 и знаков арифметических операций…

Задание #297594
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл состоит из цифр $0$, $5$, $6$, $7$ и знаков арифметических операций «$-$» и «$*$» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число $0$ не имеет знака.

В ответе укажите количество символов.

Корректное выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Число — либо одиночный $0$, либо цифра из $5$–$7$, за которой идут любые цифры набора $0$, $5$, $6$, $7$. Запрет ведущих нулей означает ровно одно: с нуля может начинаться только само число $0$.

Тонкость, которая в этом файле по-настоящему сработала: искомый фрагмент — подстрока, поэтому он может начаться в середине блока цифр. Здесь ответ как раз такой. Фрагмент стартует внутри блока $05006\ldots$, отбрасывая ведущий ноль, и начинается с цифры $5$. Если ограничиться стартами только сразу после знака операции, получится $197$ — заметно меньше правильного ответа.

Но у такого «обрезанного» старта есть плата: продолжить его влево знаком операции уже нельзя, потому что слева стоит цифра. Присоединять что-то слева можно только когда число начинается с самого начала своего блока цифр. Это и отражено в переменной chain.

Идём слева направо и для каждой позиции $j$ с цифрой считаем $L[j]$ — длину самого длинного корректного выражения, кончающегося в этой позиции. Вариантов два: либо это одно число, либо к числу слева через знак операции приклеивается уже посчитанное выражение, кончавшееся на два символа левее начала числа.

s = open('24-10.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 = r
    elif j == r:                        # само число 0
        cur = 1
        chain = r
    else:                               # блок начался с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        cur = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    # 2) приклеиваем слева выражение через знак операции
    if chain >= 2 and s[chain-1] in ops and L[chain-2] > 0:
        cur = max(cur, L[chain-2] + 1 + (j - chain + 1))

    L[j] = cur
    best = max(best, cur)

print(best)   # 211

Проверка найденного фрагмента: длина $211$, он целиком распознаётся регулярным выражением для корректной записи. Слева от него $-70$, то есть цифра — расширяться некуда. Справа фрагмент кончается на $7507$, а дальше идёт $-$, два знака подряд, что запрещено.

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

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