Задача #2043

Работа со строками

Сложнее ЕГЭ

(П. Говоров) В файле содержится строка длиной не более 10⁶ из букв A,B,D,E и цифр 0,1,2,3.
Определите в прилагаемом файле максимальную длину подпоследовательности, в которой количество согласных букв равно количеству гласных и количество четных цифр равно количеству нечетных

Файлы к задаче

Скачать 24.txt

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

286678

В задаче используется метод префиксных сумм

1) Сначала заведем списки преф. сумм для чет/нечет и гласн/согласн

2) Затем заполним их, прибавляя +1 к предыдущему, если чет или гласная (в зависимости от символа)

или -1 если нечет или согласная соответственно.

Также просто переносим предыдущее значение (не изменяя) преф сум чет/нечет если символ - буква

или преф сум гласн/согл если символ - цифра.

3) Объединим с помощью zip в 1 список (значения кортежи)

4) Найдем для всех различных "объединенных" преф сум первое и последнее вхождение в списке

5) Переберем все длины полученных отрезков и найдем макс

Код:

s = open('24.txt').readline()

pref_ch_nch = [0] * (len(s) + 1) #преф. массив чет/нечет

pref_gl_sgl = [0] * (len(s) + 1) #преф. массив гласн/согласн

for i in range(len(s)): #создаем массив преф. чет/нечет и гласн/согласн

pref_ch_nch[i+1] = pref_ch_nch[i]

pref_gl_sgl[i+1] = pref_gl_sgl[i]

if s[i] in 'AE':

pref_gl_sgl[i+1] += 1

elif s[i] in 'BD':

pref_gl_sgl[i+1] -= 1

elif s[i] in '02':

pref_ch_nch[i+1] += 1

elif s[i] in '13':

pref_ch_nch[i+1] -= 1

combined_arr = list(zip(pref_ch_nch,pref_gl_sgl)) # объединяем 2 массива в 1

first_appear = {}

#словарь 1 вхож. различных вариаций преф. чет/нечет, гл/согл

for i,j in enumerate(combined_arr):

first_appear.setdefault(j, i) #через setdefault установим только 1 вхождение

last_appear = first_appear.copy()

#словарь послед. вхож. различных вариаций преф. чет/нечет, гл/согл

for i,j in enumerate(combined_arr): #каждый раз перезаписывая знач. в словаре,

last_appear[j] = i #мы получим послед. вхож.

dop_arr = [last_appear[i] - first_appear[i] for i in first_appear.keys()]

#массив длин последовательностей с выполненным условием равности (у которых начало=1вхож, конец=посл.вхож)

print(max(dop_arr)) #ответ

Номер