Задание 24 ЕГЭ: выражение со значением 0

Самое длинное выражение со значением 0. Тема номера — обработка символьных строк. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Текстовый файл 24.txt содержит строку из не более чем 50 000 символов: десятичных цифр и знаков «+» и «*» (сложение и умножение).

Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В выражении никакие два знака операций не стоят рядом, порядок действий — по правилам математики, в записи чисел нет незначащих (ведущих) нулей; число 0 записывается одной цифрой.

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

Для выполнения этого задания следует написать программу.

Скачать файл к примеру

Решение

Сумма неотрицательных чисел равна нулю, только если каждое слагаемое равно нулю, а произведение равно нулю, только если среди множителей есть число 0. Значит, нужно самое длинное корректное выражение, в каждом слагаемом которого есть множитель 0.

Идём по строке один раз и для каждого «состояния разбора» (что прочитано последним и есть ли уже ноль в текущем слагаемом) храним самое раннее начало фрагмента. Из двух фрагментов в одном состоянии дальше выгоднее более длинный, поэтому остальные можно забыть. Регулярные выражения здесь опасны: поиск берёт самое левое совпадение, а не самое длинное.

Ответ: 172.

s = open('24.txt').read().strip()

def step(kind, z, ch):
    # kind: 'start' — ждём число, 'zero' — прочитано число 0, 'num' — число без ведущего нуля
    # z: в текущем слагаемом уже есть множитель 0
    if ch.isdigit():
        if kind == 'start':
            return ('zero', True) if ch == '0' else ('num', z)
        return ('num', z) if kind == 'num' else None
    if kind == 'start':
        return None                       # два знака подряд или знак в начале
    if ch == '*':
        return ('start', z)
    return ('start', False) if z else None  # '+': закончившееся слагаемое должно быть равно 0

best, cur = 0, {}                         # состояние -> самое раннее начало фрагмента
for j, ch in enumerate(s):
    nxt = {}
    for state, st in list(cur.items()) + [(('start', False), j)]:
        ns = step(*state, ch)
        if ns and (ns not in nxt or st < nxt[ns]):
            nxt[ns] = st
    cur = nxt
    for (kind, z), st in cur.items():
        if z and kind != 'start':
            best = max(best, j + 1 - st)
print(best)

Решить такую задачу — новый вариант с проверкой