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

ЕГЭ, Информатика: 24. Подсчет символов: все задания

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

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

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

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

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

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

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

s = open('24-21.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)   # 111

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

Показать
Очки опыта 20
Спросить Зави
22. Задание #297622
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл содержит только заглавные буквы латинского алфавита ($ABC\ldots Z$). Определите максимальное количество идущих подряд символов, среди которых каждая из букв $UVWXYZ$ встречается не более ста раз.

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

Ведём правую границу вперёд по всем символам. Если очередной символ — одна из шести отслеживаемых букв, увеличиваем её счётчик. Как только счётчик превысил $100$, подтягиваем левую границу вправо до тех пор, пока эта буква не вернётся к сотне. Сдвигая левую границу, не забываем уменьшать счётчики уходящих символов. После каждого шага правой границы обновляем ответ.

Важная деталь: условие «каждая из букв не более ста раз» — это шесть независимых ограничений, а не одно на их сумму. Считать надо шесть отдельных счётчиков.

s = open('24-22.txt').read().strip()
n = len(s)

cnt = {c: 0 for c in 'UVWXYZ'}
best = 0
L = 0

for R in range(n):
    c = s[R]
    if c in cnt:
        cnt[c] += 1
        while cnt[c] > 100:            # сужаем, пока буква c не вернётся к 100
            if s[L] in cnt:
                cnt[s[L]] -= 1
            L += 1
    best = max(best, R - L + 1)

print(best)   # 2844

Проверка найденного окна: длина $2844$, буква $U$ встречается $92$ раза, $V$ — $91$, а $W$, $X$, $Y$ и $Z$ — ровно по $100$. Слева от окна стоит $Y$, справа $Z$, то есть шаг в любую сторону даёт $101$-е вхождение соответствующей буквы. Растянуть некуда.

Файл здесь маленький, чуть больше миллиона символов, поэтому двух указателей вполне достаточно по времени.

Показать
Очки опыта 20
Спросить Зави
23. Задание #297623
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл содержит только заглавные буквы латинского алфавита ($ABC\ldots Z$). Определите максимальную длину непрерывного фрагмента, который начинается и заканчивается одной и той же буквой из первой половины алфавита (от $A$ до $M$) и не содержит эту букву внутри.

Условие «начинается и заканчивается буквой $c$, а внутри её нет» означает ровно одно: границы фрагмента — это два соседних вхождения буквы $c$. Между ними этой буквы нет по определению соседства. Значит перебирать подстроки не нужно вовсе, достаточно найти максимальный разрыв между соседними вхождениями для каждой из тринадцати букв $A$–$M$.

Делается это одним проходом. Для каждой буквы храним позицию её последнего встреченного вхождения. Встретив букву снова, сразу получаем кандидата длиной $i - last[c] + 1$: плюс один, потому что обе граничные буквы входят в длину. Затем обновляем last[c].

Буквы от $N$ до $Z$ просто игнорируем — они могут стоять внутри фрагмента сколько угодно раз, ограничение на них не распространяется.

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

last = {}          # позиция предыдущего вхождения буквы
best = 0

for i, c in enumerate(s):
    if 'A' <= c <= 'M':
        if c in last:
            best = max(best, i - last[c] + 1)   # +1 — обе границы входят в длину
        last[c] = i

print(best)   # 322

Проверка найденного фрагмента: длина $322$, он начинается и кончается буквой $M$, внутри буква $M$ не встречается ни разу.

Обратите внимание на диапазон $A$–$M$: сравнение 'A' <= c <= 'M' работает потому, что буквы идут подряд в таблице символов. Если такая запись кажется рискованной, можно написать явно c in 'ABCDEFGHIJKLM'.

Показать
Очки опыта 20
Спросить Зави
24. Задание #297630
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл состоит из заглавных букв латинского алфавита $Q$, $R$, $W$ и цифр $1$, $2$, $4$. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых ни одна буква не стоит рядом с буквой, а цифра — с цифрой.

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

Условие здесь локальное: оно ограничивает только соседние пары символов. Буква не рядом с буквой и цифра не рядом с цифрой означает ровно одно — типы символов чередуются. Конкретные значения ($Q$, $R$, $W$ или $1$, $2$, $4$) роли не играют, важен лишь признак «цифра или буква».

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

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

best = cur = 1
for i in range(1, len(s)):
    if s[i].isdigit() != s[i-1].isdigit():   # тип сменился — цепочка растёт
        cur += 1
    else:                                    # два подряд одного типа — обрыв
        cur = 1
    best = max(best, cur)

print(best)   # 17

Обратите внимание на начальное значение cur = 1: одиночный символ сам по себе условию удовлетворяет, нарушать там нечего.

Проверка найденного фрагмента: это $4W2W2R2R4Q4Q4Q2R2$, длина $17$, типы внутри действительно чередуются. Слева стоит цифра $1$, а фрагмент начинается с цифры $4$; справа стоит цифра $4$, а фрагмент кончается цифрой $2$. Ни влево, ни вправо расшириться нельзя.

Файл в этом задании совпадает с тем, что был раньше, поэтому и ответ тот же самый.

Показать
Очки опыта 20
Спросить Зави
25. Задание #297628
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $DE$ (в указанном порядке) встречается не более $240$ раз.

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

Это крайний случай, ради которого в решении стоит отдельная проверка. Буква $D$ встречается в файле всего $629$ раз при общей длине почти в миллион символов, а пара $DE$ — лишь $38$ раз, что заметно меньше разрешённых $240$. Значит ограничение не нарушается нигде, и подходящим фрагментом оказывается весь файл целиком. Ответ равен его длине.

Общая схема при этом остаётся прежней. Соберём позиции всех вхождений пары $DE$ — индексы, где стоит $D$, а следом $E$. Пара попадает в окно, только если внутри оба её символа: начало не левее $L$ и не правее $R-1$. Если вхождений больше $240$, пусть в окно попали те, что имеют номера от $i$ до $i+239$. Тогда предыдущее вхождение внутрь попасть не должно, и левая граница опускается до $occ[i-1]+1$, а следующее не должно поместиться целиком, и правая граница дотягивается до $occ[i+240]$.

s = open('24-25.txt').read().strip()
n = len(s)
K = 240

occ = [i for i in range(n-1) if s[i] == 'D' and s[i+1] == 'E']
m = len(occ)

if m <= K:                                 # ограничение нигде не нарушается
    print(n)
else:
    best = 0
    for i in range(m - K + 1):             # occ[i..i+K-1] — вхождения внутри окна
        L = occ[i-1] + 1 if i > 0 else 0   # предыдущее вхождение отсекаем
        R = occ[i+K] if i + K < m else n-1 # следующее не должно влезть целиком
        best = max(best, R - L + 1)
    print(best)

# 970249

Метод двух указателей на том же файле даёт то же самое число, что подтверждает вывод.

Здесь стоит быть внимательным с двумя вещами. Во-первых, если в программе не предусмотрена ветка для случая, когда вхождений мало, цикл окажется пустым и напечатает ноль. Полезно сразу после сбора позиций посмотреть, сколько их вообще получилось, и сверить с порогом из условия: $38$ против $240$ — разница очевидная. Во-вторых, раз ответом идёт длина всего файла, критично не захватить лишний символ. Перевода строки в конце этого файла нет, но .strip() при чтении лучше ставить всегда.

Показать
Очки опыта 20
Спросить Зави
26. Задание #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
Спросить Зави
27. Задание #297632
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Знаки операций здесь другие — вместо умножения сложение, — но на алгоритм это не влияет никак. Важно лишь то, что оба символа являются разделителями между числами, а сами по себе выражением не являются.

Отдельно отмечу оговорку «число $0$ не имеет знака». Она означает, что запись вида $+0$ или $-0$ как отдельного числа не рассматривается: знак у нас всегда бинарная операция между двумя числами, а не унарный минус или плюс. Поэтому корректное выражение обязано начинаться и заканчиваться цифрой.

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

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

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

s = open('24-26-1.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)   # 144

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

Показать
Очки опыта 20
Спросить Зави
28. Задание #297638
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Первое: числа шестиричные. Значит допустимы только цифры от $0$ до $5$, а цифры $6$, $7$, $8$, $9$ становятся такими же разделителями, как и знаки операций. Разница лишь в том, что через знак операции выражение можно продолжить влево, а через цифру $7$ — нельзя.

Второе, главное: порядок действий слева направо должен совпадать с математическим. Умножение приоритетнее вычитания, поэтому расхождение возникает ровно тогда, когда после какого-то вычитания дальше встречается умножение. Математика выполнила бы это умножение раньше, а чтение слева направо — позже. Значит корректная запись имеет жёсткую форму: сначала идут все умножения, потом все вычитания. Схематично это число, затем группа $*$-звеньев, затем группа $-$-звеньев.

Отсюда динамика на два состояния. Для каждой позиции $j$, где кончается число, считаем $M[j]$ — длину самого длинного выражения, в котором пока встречались только умножения, и $S[j]$ — длину самого длинного выражения, где вычитания уже начались. Переход через $*$ разрешён только из состояния $M$ в $M$, переход через $-$ — из любого состояния в $S$. Обратной дороги нет: попав в $S$, умножение уже не приписать.

Число — либо одиночный $0$, либо цифра из $1$–$5$, за которой идут цифры $0$–$5$. Фрагмент может начаться в середине цепочки цифр, отбросив ведущие нули, но тогда продолжить его влево знаком операции нельзя, слева стоит цифра. Это отражает переменная chain.

s = open('24-28.txt').read().strip()
n = len(s)
dig = set('012345')          # цифры 6-ричной системы

M = [0] * n                  # выражение только с умножениями
S = [0] * n                  # выражение, где уже начались вычитания
best = 0
r = 0                        # начало текущей цепочки 6-ричных цифр

for j in range(n):
    if s[j] not in dig:      # знак операции или цифра 6..9 — обрыв цепочки
        r = j + 1
        continue

    # число, кончающееся в позиции j
    if s[r] != '0':
        num_len = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        num_len = 1
        chain = r
    else:                               # цепочка началась с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        num_len = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    m, sm = num_len, 0                  # одно число — уже верное выражение
    if chain >= 2 and s[chain-2] in dig:
        prev = s[chain-1]
        if prev == '*' and M[chain-2] > 0:          # умножение только после умножений
            m = max(m, M[chain-2] + 1 + num_len)
        if prev == '-':                             # вычитание можно после любого
            base = max(M[chain-2], S[chain-2])
            if base > 0:
                sm = base + 1 + num_len

    M[j], S[j] = m, sm
    best = max(best, m, sm)

print(best)   # 51

Проверка найденного фрагмента: это $3021!!1!!1!!1!!1!!2!!3!!3!!4!!2!-!25430!-!451!-!12!-!12!-!4431!-!0!-!0!-!0!-!1$, длина $51$. Хорошо видна требуемая структура: сначала блок умножений, потом блок вычитаний. Слева от фрагмента стоит цифра $4$, справа после последней единицы идёт $-$, два знака подряд.

Показать
Очки опыта 20
Спросить Зави
29. Задание #297636
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Сначала о самом файле. В нём пять строк: первые три — текст условия, и только четвёртая содержит данные, ровно $10$ миллионов символов. Читать файл целиком нельзя, иначе цифры из фразы про $8$-ричные числа попадут в обработку. Берём именно строку с данными.

Числа восьмеричные, значит допустимы только цифры от $0$ до $7$, а цифры $8$ и $9$ становятся разделителями наравне со знаками операций. Разница между ними одна: через знак операции выражение продолжается влево, а через цифру $9$ — нет.

Порядок действий слева направо должен совпадать с математическим. Умножение приоритетнее вычитания, поэтому расхождение возникает ровно тогда, когда после какого-то вычитания дальше встречается умножение: математика выполнила бы его раньше, а чтение слева направо — позже. Значит корректная запись имеет жёсткую форму: сначала все умножения, потом все вычитания.

Отсюда динамика на два состояния. Для каждой позиции $j$, где кончается число, считаем $M[j]$ — длину самого длинного выражения, где пока были только умножения, и $S[j]$ — длину самого длинного выражения, где вычитания уже начались. Переход через $*$ возможен только из $M$ в $M$, переход через $-$ — из любого состояния в $S$. Обратной дороги нет: попав в $S$, умножение уже не приписать.

Число — либо одиночный $0$, либо цифра из $1$–$7$, за которой идут цифры $0$–$7$. Фрагмент может начаться в середине цепочки цифр, отбросив ведущие нули, но тогда влево его знаком операции не продолжить, слева стоит цифра. Это отражает переменная chain.

s = open('24-29.txt', encoding='utf-8').read().split('\n')[3]   # строка с данными
n = len(s)
dig = set('01234567')        # цифры 8-ричной системы

M = [0] * n                  # выражение только с умножениями
S = [0] * n                  # выражение, где уже начались вычитания
best = 0
r = 0                        # начало текущей цепочки 8-ричных цифр

for j in range(n):
    if s[j] not in dig:      # знак операции или цифра 8, 9 — обрыв цепочки
        r = j + 1
        continue

    # число, кончающееся в позиции j
    if s[r] != '0':
        num_len = j - r + 1
        chain = r
    elif j == r:                        # само число 0
        num_len = 1
        chain = r
    else:                               # цепочка началась с 0 — стартуем с первой ненулевой
        q = r
        while q <= j and s[q] == '0':
            q += 1
        num_len = j - q + 1 if q <= j else 1
        chain = -1                      # слева цифра, знак операции не приписать

    m, sm = num_len, 0                  # одно число — уже верное выражение
    if chain >= 2 and s[chain-2] in dig:
        prev = s[chain-1]
        if prev == '*' and M[chain-2] > 0:          # умножение только после умножений
            m = max(m, M[chain-2] + 1 + num_len)
        if prev == '-':                             # вычитание можно после любого
            base = max(M[chain-2], S[chain-2])
            if base > 0:
                sm = base + 1 + num_len

    M[j], S[j] = m, sm
    best = max(best, m, sm)

print(best)   # 71

Проверка найденного фрагмента: это $61246!!25450!!0!!0!!0!!0!!0!!0!!0!!0!!163!!465!!2600!-!354324063!-!565!-!566!-!6!-!0!-!0!-!0!-!2600$, длина $71$. Требуемая структура видна сразу: блок умножений, затем блок вычитаний. Слева стоит цифра $3$, справа после последнего $2600$ идёт $*$, а умножение после вычитаний уже невозможно.

Показать
Очки опыта 20
Спросить Зави
30. Задание #297641
Решено верно
Решено неверно
Сообщить о проблеме

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального нечётного $14$-ричного числа.

В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности. Примечание. Латинские буквы $A$, $B$, $C$ и $D$ означают цифры из алфавита $14$-ричной системы счисления.

Разбираем условие на три требования к искомой подстроке.

Во-первых, это запись числа в системе с основанием $14$, значит все символы обязаны принадлежать алфавиту $0–9$, $A$, $B$, $C$, $D$. Любая буква от $E$ до $Z$ — разделитель, и строка распадается на блоки допустимых символов.

Во-вторых, число нечётное. Основание $14$ чётно, поэтому все разряды кроме последнего дают чётный вклад, и чётность числа определяется только последней цифрой. Нечётные цифры алфавита: $1$, $3$, $5$, $7$, $9$, $B$ (это $11$) и $D$ (это $13$). Значит подстрока обязана заканчиваться на одну из них. Обратите внимание, что буквы тоже участвуют: $B$ и $D$ нечётны, а $A$ и $C$ — нет.

В-третьих, «значащих цифр» означает запрет ведущего нуля: первым символом не может быть $0$.

Число тем больше, чем больше в нём разрядов, поэтому сначала максимизируем длину. Внутри блока самое левое допустимое начало — первая ненулевая цифра, самый правый допустимый конец — последняя нечётная цифра. При совпадении длин сравниваем сами записи как строки, что при равной длине равносильно сравнению по величине.

import re

s = open('24-30.txt').read().strip()
odd = set('13579BD')             # нечётные цифры 14-ричной системы

best_len, best_val = 0, ''
for m in re.finditer(r'[0-9A-D]+', s):     # блоки из допустимых символов
    b = m.group()

    i = 0                                  # первая ненулевая цифра
    while i < len(b) and b[i] == '0':
        i += 1
    if i == len(b):
        continue

    j = len(b) - 1                         # последняя нечётная цифра
    while j >= i and b[j] not in odd:
        j -= 1
    if j < i:
        continue

    cand = b[i:j+1]
    if len(cand) > best_len or (len(cand) == best_len and cand > best_val):
        best_len, best_val = len(cand), cand

print(best_len)   # 2599

Проверка: самый длинный блок допустимых символов имеет длину $2600$, после отсечения ведущего нуля слева и чётного хвоста справа остаётся $2599$ символов, запись начинается с $8$ и кончается на $7$. Ближайший конкурент даёт лишь $1219$, так что сравнение по величине не понадобилось.

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

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