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

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

Сообщить о проблеме
Задание #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
Спросить Зави
0 заданий сегодня

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