Что спрашивают
Строка содержит цифры, плюсы и звёздочки. Нужно найти самый длинный непрерывный фрагмент, являющийся корректным выражением со значением ноль. Числа неотрицательные, умножение выполняется раньше сложения. Одно число тоже считается выражением.
Операторы не могут стоять рядом или на краю. В числах нет ведущих нулей: самостоятельный 0 допустим, а 00 или 012 — нет. Подходящий фрагмент существует.
Приём решения
Сумма неотрицательных произведений равна нулю, только если каждое слагаемое равно нулю. Произведение равно нулю, если хотя бы один его множитель — число 0. Поэтому вычислять огромные числовые значения не нужно: достаточно помнить, стало ли текущее произведение нулевым.
Остаётся проверить запись чисел и знаков. После числа 0 нельзя приписать ещё цифру, иначе возникнут ведущие нули. После числа, начавшегося ненулевой цифрой, приписывать цифры можно. Звёздочка сохраняет признак нулевого произведения, а плюс разрешён только после уже нулевого слагаемого и начинает новое произведение.
| Состояние | Что уже прочитано |
|---|---|
| zero | Текущее число — отдельный 0; произведение нулевое. |
| number_zero | Текущее число ненулевое; ранее в этом произведении был множитель 0. |
| number_other | Текущее число ненулевое; нулевого множителя пока нет. |
| after_zero | Прочитан * после нулевого произведения; ждём число. |
| after_other | Прочитан * после ненулевого произведения; ждём число. |
| after_plus | Прочитан + после нулевого слагаемого; ждём новое число. |
В каждом состоянии храним самый ранний индекс начала выражения, которое дошло до этого состояния; недостижимое состояние обозначаем len(s) + 1. Если несколько фрагментов имеют одинаковое состояние, оставляем самый ранний: их возможные продолжения одинаковы, а он даёт большую длину.
- Для каждой цифры разрешите начать новое выражение с текущей позиции и продолжить допустимые старые состояния.
- На звёздочке переводите законченные числа в ожидание следующего множителя.
- На плюсе продолжайте только уже нулевое произведение; два оператора подряд обнуляют все старые варианты.
- Ответ обновляйте только в состояниях zero и number_zero: запись закончена числом и её значение равно нулю.
Ненулевое текущее произведение пока не отбрасываем: следующий множитель 0 может сделать его нулевым. Все прежние слагаемые при этом уже обязаны быть нулевыми. Состояний всегда шесть, так что время — O(n), дополнительная память — O(1). Алгоритм не преобразует длинные числа в int и не выполняет текст через eval.
Разбор на примере
Ввод
00*12+0*4++8*0
Вывод
8
| Фрагмент | Длина | Проверка |
|---|---|---|
| 00 | 2 | Ведущие нули: нельзя |
| 0*12+0*4 | 8 | Два нулевых произведения: подходит |
| ++ | 2 | Разрыв корректной записи |
| 8*0 | 3 | Подходит, но короче |
Первый ноль нельзя включить вместе со вторым как число 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')))
<algorithm>
<iostream>
<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. До плюса храните такой вариант отдельно от уже нулевого произведения.
- Перебирать и вычислять все подстроки
При миллионе символов это слишком много кандидатов. Конечное число состояний заменяет повторный разбор полных фрагментов.