Что спрашивают

Строка содержит цифры, плюсы и звёздочки. Нужно найти самый длинный непрерывный фрагмент, являющийся корректным выражением со значением ноль. Числа неотрицательные, умножение выполняется раньше сложения. Одно число тоже считается выражением.

Операторы не могут стоять рядом или на краю. В числах нет ведущих нулей: самостоятельный 0 допустим, а 00 или 012 — нет. Подходящий фрагмент существует.

Приём решения

Сумма неотрицательных произведений равна нулю, только если каждое слагаемое равно нулю. Произведение равно нулю, если хотя бы один его множитель — число 0. Поэтому вычислять огромные числовые значения не нужно: достаточно помнить, стало ли текущее произведение нулевым.

Остаётся проверить запись чисел и знаков. После числа 0 нельзя приписать ещё цифру, иначе возникнут ведущие нули. После числа, начавшегося ненулевой цифрой, приписывать цифры можно. Звёздочка сохраняет признак нулевого произведения, а плюс разрешён только после уже нулевого слагаемого и начинает новое произведение.

СостояниеЧто уже прочитано
zeroТекущее число — отдельный 0; произведение нулевое.
number_zeroТекущее число ненулевое; ранее в этом произведении был множитель 0.
number_otherТекущее число ненулевое; нулевого множителя пока нет.
after_zeroПрочитан * после нулевого произведения; ждём число.
after_otherПрочитан * после ненулевого произведения; ждём число.
after_plusПрочитан + после нулевого слагаемого; ждём новое число.

В каждом состоянии храним самый ранний индекс начала выражения, которое дошло до этого состояния; недостижимое состояние обозначаем len(s) + 1. Если несколько фрагментов имеют одинаковое состояние, оставляем самый ранний: их возможные продолжения одинаковы, а он даёт большую длину.

  1. Для каждой цифры разрешите начать новое выражение с текущей позиции и продолжить допустимые старые состояния.
  2. На звёздочке переводите законченные числа в ожидание следующего множителя.
  3. На плюсе продолжайте только уже нулевое произведение; два оператора подряд обнуляют все старые варианты.
  4. Ответ обновляйте только в состояниях zero и number_zero: запись закончена числом и её значение равно нулю.

Ненулевое текущее произведение пока не отбрасываем: следующий множитель 0 может сделать его нулевым. Все прежние слагаемые при этом уже обязаны быть нулевыми. Состояний всегда шесть, так что время — O(n), дополнительная память — O(1). Алгоритм не преобразует длинные числа в int и не выполняет текст через eval.

Разбор на примере

Ввод

00*12+0*4++8*0

Вывод

8
Разбор примера по шагам
ФрагментДлинаПроверка
002Ведущие нули: нельзя
0*12+0*48Два нулевых произведения: подходит
++2Разрыв корректной записи
8*03Подходит, но короче

Первый ноль нельзя включить вместе со вторым как число 00. Начав со второго символа, получаем 0*12+0*4: оба слагаемых нулевые, запись корректна, длина восемь. Пара плюсов разрывает выражение. Справа остаётся ещё один подходящий фрагмент 8*0, но его длина только три.

Код на Python и C++

Входной алфавит ограничен цифрами, + и *. Значения состояний — индексы начала, а не числа из выражения. Временные new-переменные нужны, чтобы переходы использовали старые состояния.

В C++ минимум из нескольких значений записывается с фигурными скобками: min({i, after_zero, after_other, after_plus}).

import sys


def solve(s):
    inf = len(s) + 1
    zero = number_zero = number_other = inf
    after_zero = after_other = after_plus = inf
    best = 0
    for i, ch in enumerate(s):
        if ch.isdigit():
            if ch == '0':
                new_zero = min(i, after_zero, after_other, after_plus)
                new_number_zero = number_zero
                new_number_other = number_other
            else:
                new_zero = inf
                new_number_zero = min(number_zero, after_zero)
                new_number_other = min(i, number_other, after_other, after_plus)
            zero = new_zero
            number_zero = new_number_zero
            number_other = new_number_other
            after_zero = after_other = after_plus = inf
            start = min(zero, number_zero)
            if start != inf:
                best = max(best, i - start + 1)
        elif ch == '*':
            after_zero = min(zero, number_zero)
            after_other = number_other
            after_plus = inf
            zero = number_zero = number_other = inf
        else:
            after_plus = min(zero, number_zero)
            after_zero = after_other = inf
            zero = number_zero = number_other = inf
    return best

if __name__ == '__main__':
    print(solve(sys.stdin.readline().rstrip('\r\n')))
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int solve(const string& s) {
    int n = s.size(), inf = n + 1;
    int zero = inf, number_zero = inf, number_other = inf;
    int after_zero = inf, after_other = inf, after_plus = inf;
    int best = 0;
    for (int i = 0; i < n; i++) {
        char ch = s[i];
        if ('0' <= ch && ch <= '9') {
            int new_zero, new_number_zero, new_number_other;
            if (ch == '0') {
                new_zero = min({i, after_zero, after_other, after_plus});
                new_number_zero = number_zero;
                new_number_other = number_other;
            } else {
                new_zero = inf;
                new_number_zero = min(number_zero, after_zero);
                new_number_other = min({i, number_other, after_other, after_plus});
            }
            zero = new_zero;
            number_zero = new_number_zero;
            number_other = new_number_other;
            after_zero = after_other = after_plus = inf;
            int start = min(zero, number_zero);
            if (start != inf)
                best = max(best, i - start + 1);
        } else if (ch == '*') {
            after_zero = min(zero, number_zero);
            after_other = number_other;
            after_plus = inf;
            zero = number_zero = number_other = inf;
        } else {
            after_plus = min(zero, number_zero);
            after_zero = after_other = inf;
            zero = number_zero = number_other = inf;
        }
    }
    return best;
}

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    cout << solve(s) << endl;
}

Типичные ошибки

  • Проверить только правильность знаков

    Корректно записанное выражение не обязано равняться нулю. Каждое слагаемое должно содержать отдельный нулевой множитель.

  • Принять любую цифру 0 за нулевой множитель

    Число 102 содержит ноль, но само не равно нулю. Нулевой множитель должен быть отдельным числом 0.

  • Разрешить ведущие нули

    После самостоятельного 0 следующая цифра начинает новый кандидат, а не продолжает то же число.

  • Сразу отбросить ненулевое произведение

    Его ещё можно умножить на 0. До плюса храните такой вариант отдельно от уже нулевого произведения.

  • Перебирать и вычислять все подстроки

    При миллионе символов это слишком много кандидатов. Конечное число состояний заменяет повторный разбор полных фрагментов.