A9D03C — Обработка текстового файла: ответ и решение

СВОЙСТВА ЗАДАНИЯ

КЭС:

2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа)

2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат

3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве

3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива

3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста

3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных

3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры

3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева

Тип ответа:

Краткий ответ

Номер: A9D03C

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFA9D03C

Ответ: 84

Запрещена соседняя пара, в которой обе буквы принадлежат набору A, B, C. Совпадающие буквы тоже учитываются: AA запрещено. Одиночные A, B, C допустимы. Например, ADB подходит целиком, а ABC разбивается на отдельные символы.
Пусть current — длина самого длинного допустимого фрагмента, заканчивающегося на текущем символе. Для первого символа она равна 1. Если новая соседняя пара разрешена, прежний фрагмент продлевается: current увеличивается на 1. Если пара запрещена, начинаем с текущего символа заново: current = 1.
После каждого символа обновляем общий максимум best. Обязательно делаем это и на последнем символе: иначе можно потерять самую длинную серию в конце файла. Перевод строки не относится к алфавиту задачи, поэтому убираем его с помощью strip.
Сохраните скачанный файл под именем 1_24.txt рядом с программой. Полная программа на Python 3:

s = open('1_24.txt', encoding='utf-8').read().strip()
current = 0
best = 0
for i in range(len(s)):
    if i == 0:
        current = 1
    else:
        forbidden = s[i - 1] in 'ABC' and s[i] in 'ABC'
        if forbidden:
            current = 1
        else:
            current += 1
    best = max(best, current)
print(best)

Программа выводит 84. Для вычисления достаточно одного прохода по строке.
Проверка корректности. В уже найденном фрагменте все соседние пары допустимы. После добавления символа нужно проверить только новую последнюю пару. Если она запрещена, любой более длинный фрагмент с тем же концом содержит её и тоже запрещён. Следовательно, правило обновления находит максимальную длину для каждого возможного конца.
Независимая проверка состоит в разрезании исходной строки по всем запрещённым соседним парам. Каждая полученная часть допустима, а любой допустимый фрагмент целиком лежит в одной из частей. Поэтому максимум их длин должен совпасть с результатом программы.

Характеристика	Значение
Символов в файле	10000000
Частей между запрещёнными границами	2027257
Максимальная длина	84

Максимальный фрагмент расположен на позициях 8622517–8622600, если считать с 1. Его длина 8622600 − 8622517 + 1 = 84.
Контрольный фрагмент разбит ниже на четыре последовательные части по 21 символу. Соединение частей без пробелов восстанавливает исходные 84 символа.

Позиции в фрагменте	Символы
1–21	ADMYCEGYDTQWZXUXXGBFE
22–42	NQSCHTXBXRDAJBXATMOQB
43–63	NERCGVKHKRCNBTYCKRDAK
64–84	AKAOWBMPUTDNNCWTCVEMB

На левой границе стоят символы AA, на правой — BC. Обе пары запрещены, поэтому фрагмент нельзя продлить. Сравнение всех частей подтверждает, что более длинных нет.
Ответ: 84.

Задание EGEINFA9D03C: Обработка текстового файла

Решение задания EGEINFA9D03C

Помочь улучшить сайт

Комментарии к решению