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

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

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

Текстовый файл состоит из цифр от $1$ до $6$, знаков операций «$-$» и «$*$» (вычитание и умножение) и заглавных латинских букв $A$, $B$, $C$, $D$. Определите максимальное количество символов в непрерывной последовательности символов, состоящей из буквы $A$, за которой следует корректное арифметическое выражение с целыми неотрицательными числами, записанными в десятичной системе счисления.

Задача проще предыдущих на выражения, и вот почему. Цифра $0$ в файле отсутствует вовсе, значит вопрос о ведущих нулях снимается сам собой: любая непустая цепочка цифр — корректное число. Кроме того, старт жёстко зафиксирован буквой $A$, никакой свободы выбора левой границы нет.

Значит алгоритм такой. Находим каждую букву $A$ и пытаемся прочитать сразу за ней максимально длинное корректное выражение. Выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Буквы $B$, $C$, $D$ и сама $A$ внутрь попасть не могут, они обрывают чтение.

Удобнее всего доверить чтение регулярному выражению: жадный поиск сам возьмёт самый длинный корректный кусок и откатится назад, если наткнётся на два знака подряд или на букву сразу после знака. Длина ответа — это длина выражения плюс единица на саму букву $A$.

import re

s = open('24-27.txt').read().strip()
pat = re.compile(r'[1-6]+(?:[-*][1-6]+)*')   # число (знак число)*

best = 0
for m in re.finditer('A', s):
    i = m.start()
    e = pat.match(s, i + 1)                  # читаем выражение сразу за A
    if e:
        best = max(best, 1 + (e.end() - i - 1))   # +1 — сама буква A

print(best)   # 85

Проверка найденного фрагмента: длина $85$, начинается он с буквы $A$, а остаток целиком распознаётся как корректное выражение. Кончается фрагмент на $543$, а дальше в файле идёт $—B$: два знака подряд, поэтому продлить его нельзя.

Если бы в алфавите присутствовал ноль, задача усложнилась бы ровно на один пункт — пришлось бы отдельно разбирать числа с ведущими нулями, как в разборах выше.

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

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