Не могу решить задачку ЕГЭ

Question

Задача:

Текстовый файл состоит не более чем из 10^6 символов X, Y и Z. Определите максимальную длину цепочки вида XYZXYZXYZ... (составленной из фрагментов XYZ, последний фрагмент может быть неполным).

Мой код с попыткой решения:

f = open("zadanie24_var_4.txt")
s = f.read()
m = 1
maxlen = 1
for i in range(len(s) - 1):
    if s[i] == "X" and m%3 == 0 or \
    s[i + 1] == "Y" and m%3 == 1 or \
    s[i + 2] == "Z" and m%3 == 2:
        m += 1
        if maxlen < m:
            maxlen = m
    elif s[i] == "X":
        m = 1
    else:
        m = 0
print(maxlen)

Ответ, который выдаёт моя программа - 10, а надо 13.

Answer 1

вы не учитываете последний неполный фрагмент -

попробуйте свой код на s = "AXYZXA" - тут длина цепочки 2, а не 1,

когда прерывается последовательность и надо оценивать длину последовательности, а вы оцениваете только когда она наращивается, в итоге последнее неполное звено вы никак не можете учесть

вот решение в лоб (вроде как):

s = "AXYZXA"

maxlen = 0 # максимальное кол-во последовательных звеньев XYZ и неполных окончаний

pos = 0 # позиция в строке
count = 0 # текущее кол-во последовательных звеньев XYZ и неполных окончаний

while pos < len(s):

    # извлекаем (срез) 3 символа из строки от позиции pos до позиции pos + 3
    # если срез равен "XYZ" - увеличиваем текущее кол-во последовательных звеньев XYZ и перемещаем позицию на 3 символа вперед    
    if s[pos:pos + 3] == "XYZ":
        count += 3
        pos += 3
    else:
        # извлекаем (срез) 3 символа из строки от позиции pos до позиции pos + 2
        # если срез равен "XY" - увеличиваем текущее кол-во последовательных звеньев XYZ (поскольку XY - это неполное окончание) и перемещаем позицию на 2 символа вперед    
        if s[pos:pos + 2] == "XY":
            count += 2
            pos += 2
        elif s[pos:pos + 1] == "X":
            count += 1
            pos += 1
        else:
            pos += 1

        # поскольку извлеченный срез соответствует неполному окончанию звена XYZ, то прекращаем увеличивать счетчик звеньев (последовательность закончилась)
        # определяем превышает ли текущий счетчик звеньев максимальное значение и сбрасываем локальный счетчик в 0
        maxlen = count if count > maxlen else maxlen
        count = 0

# определяем превышает ли текущий счетчик звеньев максимальное значение и сбрасываем локальный счетчик в 0
# после окончания цикла данная проверка нужна поскольку строка может оканчиваться на "XYZ" и не будет выполнена проверка на максиму
maxlen = count if count > maxlen else maxlen

print(maxlen)

кстати подумалось, что код можно облегчить так (чтобы снаружи цикла не весело лишних проверок):

s = "AXYZXA"

maxlen = 0

pos = 0
count = 0

while pos < len(s):

    if s[pos:pos + 3] == "XYZ":
        count += 3
        pos += 3
    else:
        if s[pos:pos + 2] == "XY":
            count += 2
            pos += 2
        elif s[pos:pos + 1] == "X":
            count += 1
            pos += 1
        else:
            pos += 1

    maxlen = count if count > maxlen else maxlen

    if s[pos:pos + 3] != "XYZ":
        count = 0
    
print(maxlen)

Answer 2

if s[i] == "X" and m%3 == 0 or s[i] == "Y" and m%3 == 1 or s[i] == "Z" and m%3 == 2:

Answer 3

https://ideone.com/amB3uF, https://ideone.com/9Z25K1

import re

print(max((len(s) for s in re.findall(r"X(?:YZX)*(?:YZ?)?", input())), default=0))

По идее асимптотика тут линейная.

Answer 4

Реализация через конечный автомат. Иногда (но только иногда) она догоняет реализацию через регулярные выражения:

def max_xyz_length_fsm(s):

    def lengths_ending_here():
        expected_state = {'Y': 'X', 'Z': 'Y', 'X': 'Z'}

        state = '*'
        length = 0

        for c in s:
            if expected_state[c] == state:
                length += 1
                state = c
            elif c == 'X':
                length = 1
                state = 'X'
            else:
                length = 0
                state = '*'
            yield length

    return max(lengths_ending_here(), default=0)

Answer 5

https://ideone.com/gqRcsl

cur = 0
res = 0
i = 0
seq = 'XYZ'

for ch in input():
  if ch == seq[i]:
    cur = cur + 1
    i = (i + 1) % len(seq)
  else:
    res = max(res, cur)
    cur = +(ch == seq[0])
    i = cur

res = max(res, cur)

print(res)

БЛОГ НА HUSL

Не могу решить задачку ЕГЭ

Ответы (5 шт):