Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите...

Задание:

Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз.

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

Примечание: файлы в архиве с демоверсией ЕГЭ-2024 по информатике

Решение (программное, через разбивку)

Описание алгоритма:

1) Разбиваем строку по букве T, сохраняя при этом пустые подстроки, которые расположены в оригинальной строке между подряд идущими буквами T.

2) Находим суммы длин всех подряд идущих 101 подстрок. Эти строки, при объединении их через T, будут содержать ровно 100 букв T.

3) Среди найденных сумм находим наибольшую и добавляем 100 (100 не входящих в полученные подстроки букв T).

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

# сохраняем только длины получившихся подстрок
word_len = [len(x) for x in s.split('T')]

# если количество слов меньше 101, таких строк нет
if len(word_len) < 101:
   print(0)
else:
   # срез позволяет не делать проверку
   # на количество слов, меньшее 101
   len101 = [sum(word_len[i:i+101]) for i in range(len(word_len))]

print(max(len101) + 100) 

Вывод: 133

Решение (динамическое программирование)

Описание алгоритма:

1) Будем сохранять индексы последних 101 букв Т (изначально все индексы будут -1).

2) При нахождении каждой следующей Т будем считать расстояние от найденной Т до предыдущей (на 101 левее) Т. Начальные значения -1 будут указывать на начало строки.

3) Если количество букв Т меньше 100, то выведем 0. Для обобщения обработки последнего фрагмента в строке допишем к ней справа одну T. Так алгоритм, обрабатывающий предшествующие 100 Т правильно обработает окончание строки.

Пример для обработки трех Т. Для max_len указано число только в случае обновления максимальной длины строки.

Задана строка: WUTTUXTTXXUTUUWXWTTTXUTUU
Дописываем Т: WUTTUXTTXXUTUUWXWTTTXUTUUT

Изначально список pos_t содержит [-1, -1, -1, -1].

s = open('24_2024.txt').readline() + 'T'
pos_t = [-1]*101
cnt_t = 0
mx_len = 0

for i in range(len(s)):
  if s[i] == 'T':
   cnt_t += 1
   mx_len = max(mx_len, i - pos_t[cnt_t % 101] - 1)
   pos_t[cnt_t % 101] = i

if cnt_t >= 100:
  print(mx_len)
else:
  print(0) 

Вывод: 133

Также можно несколько упростить алгоритм, утяжелив его хранением всех индексов точек

s = open('24_2024.txt').readline() + 'T'
pos_t = [-1]

for i in range(len(s)):
  if s[i] == 'T':
   pos_t.append(i)

if len(pos_t) <= 100:
  print(0)
else:
  max_len = 0
  for i in range(101, len(pos_t)):
   max_len = max(max_len, pos_t[i] - pos_t[i-101] - 1)

print(max_len) 

Вывод: 133

Источник: Информатика с Джобсом | ЕГЭ