Задача Задача №2008041
А
А
Сегодня на уроке информатики Данила узнал, что слова можно сравнивать в лексикографическом (алфавитном) порядке. Лексикографический порядок слов это способ их упорядочивания, аналогичный расположению в словаре. Сравнение слов при этом осуществляется по следующим правилам. Сравнение букв: сначала сравниваются первые символы слов. Слово, первый символ которого стоит раньше в алфавите, считается меньшим. Например, слово «яблоко» будет стоять после слова «груша», потому что «я» стоит позже «г». Длина слов: если два слова начинаются с одинаковых букв, то дальше сравниваются их символы по порядку. Если одно слово является префиксом другого (например, «кот» и «котёнок»), то более короткое слово считается меньшим, даже если они совпадают до определенной позиции. Примеры: «собака» < «собачка» «дерево» < «долина» «апельсин» > «ананас Такая система упорядочивания полезна для сортировки списков слов, поиска и обработки текстовой информации. В процессе подготовки к олимпиаде по информатике Данила написал на полоске бумаги слово «СИРИУСОЛИМП», разрезал полоску в и местах и переставил получившиеся куски местами (все получившиеся части исходного слова были использованы). Он мечтает сделать исходный «СИРИУСОЛИМП» как можно большим. Ответьте на вопросы. 1) Какое наибольшее слово в лексикографическом порядке он может получить при п = 1 (то есть сделав единственный разрез)?
Для того чтобы найти наибольшее слово в лексикографическом порядке, которое Данила может получить, сделав единственный разрез в слове «СИРИУСОЛИМП», необходимо рассмотреть все возможные разрезы и затем соединить части в различных комбинациях.
Слово «СИРИУСОЛИМП» состоит из 12 букв. Если Данила сделает один разрез, получится две части. Мы будем рассматривать все возможные позиции разреза:
- После первой буквы: «С» и «ИРИУСОЛИМП» → получается слово «СИРИУСОЛИМП».
- После второй буквы: «СИ» и «РИУСОЛИМП» → не получится.
- После третьей буквы: «СИР» и «ИУСОЛИМП» → не получится.
- После четвёртой буквы: «СИРИ» и «УСОЛИМП» → не получится.
- После пятой буквы: «СИРИУ» и «СОЛИМП» → не получится.
- После шестой буквы: «СИРИУС» и «ОЛИМП» → не получится.
- После седьмой буквы: «СИРИУСО» и «ЛИМП» → не получится.
- После восьмой буквы: «СИРИУСОЛ» и «ИМП» → не получится.
- После девятой буквы: «СИРИУСОЛИ» и «МП» → не получится.
- После десятой буквы: «СИРИУСОЛИМ» и «П» → не получится.
Теперь рассмотрим каждую пару:
- «С» + «ИРИУСОЛИМП» = «СИРИУСОЛИМП»
- Объединяем вариант, который остался: «СИЛИМП»
- Продолжать в том же духе.
В итоге, если мы составим пары из разрезов, мы увидим, что максимальным вариантом, который можно получить — это «СРИУСОЛИМП».
Оптимальный вариант после разреза в позиции между буквой «С» и буквой «И».
Ответ: «СРИУСОЛИМП».
