Задание 24 ЕГЭ по информатике

9712

Программное решение при помощи алгоритма двух указателей:

with open('24.txt') as f:
    s = f.readline()

left = 0
max_ss_cd = 0
count_cd = 0
for right in range(len(s) - 1):
    if s[right:right + 2] == 'CD':
        count_cd += 1
    while count_cd == 161:
        max_ss_cd = max(max_ss_cd, right - left + 1)
        if s[left:left + 2] == 'CD':
            count_cd -= 1
        left += 1

print(max_ss_cd)

Ответ: 9712.

Программное решение при помощи разбиения по паре CE:

with open('24.txt') as f:
    s = f.readline()

sub_strs = s.split('CD')

max_ss_cd = 0
for i in range(len(sub_strs) - 161):
    # Из полученных подстрок после разбиения берем наборы по 161 штуке,
    # так как максимальная подстрока с 160-ю 'CD' начинается с 'C' и заканчивается 'D',
    # то есть начинается с конца сочетания 'CD' и заканчивается началом сочетания 'CD'
    curr_substr = sum(len(ss) for ss in sub_strs[i:i + 161])
    max_ss_cd = max(max_ss_cd, curr_substr + 2 * 160 + 2)

print(max_ss_cd)

Ответ: 9712.