Как решить: Сегодня на уроке информатики Данила узнал, что слова...?
Разрезание строки
Сегодня на уроке информатики Данила узнал, что слова можно сравнивать в лексикографическом (алфавитном) порядке.
Лексикографический порядок слов - это способ их упорядочивания, аналогичный расположению в словаре. Сравнение слов при этом осуществляется по следующим правилам.
Сравнение букв: сначала сравниваются первые символы слов. Слово, первый символ которого стоит раньше в алфавите, считается меньшим. Например, слово «яблоко» будет стоять после слова «груша», потому что «я» стоит позже «г».
Длина слов: если два слова начинаются с одинаковых букв, то дальше сравниваются их символы по порядку. Если одно слово является префиксом другого (например, «кот» и «котёнок»), то более короткое слово считается меньшим, даже если они совпадают до определённой позиции.
Примеры: «собака» < «собачка», «дерево» < «долина», «апельсин» > «ананас». Такая система упорядочивания полезна для сортировки списков слов, поиска и обработки текстовой информации.
В процессе подготовки к олимпиаде по информатике Данила написал на полоске бумаги слово «СИРИУСОЛИМП», разрезал полоску в n местах и переставил получившиеся куски местами (все получившиеся части исходного слова были использованы). Он мечтает сделать исходный «СИРИУСОЛИМП» как можно большим.
Ответьте на вопросы.
1) Какое наибольшее слово в лексикографическом порядке он может получить при n=1 (то есть сделав единственный разрез)?
2) Какое наибольшее слово в лексикографическом порядке он может получить при n=2?
3) Какое наибольшее слово в лексикографическом порядке он может получить при n=3?
4) Какое наименьшее количество разрезов необходимо сделать, чтобы получить из «СИРИУСОЛИМП» наибольшее лексикографическое слово?
Каждый верный ответ даст 25 баллов. Менее точные ответы будут оцениваться меньшим количеством баллов.
Буквы русского алфавита (для справки): АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.
Ответы (3)
Длинное описательное условие, а ответ будет гораздо короче.
1) При одном разрезе: Самая старшая буква из всех предложенных это "У". С неё будет начинаться слово. Потому отрезаем перед ней и переставляем.
Потому будет слово
"УСОЛИМП | СИРИ"
2) При двух разрезах: Можно отрезать буквы "УС" и вставить перед первой "С"
Получим слово
"УС | СИРИ | ОЛИМП"
3) При трех разрезах: Отрезаем "УС" и ещё первую "С". И тогда можно вставить их в следующем порядке:
"УС | С | ОЛИМП | ИРИ"
4) Для решения сначала напишем это максимальное слово расставив буквы по не возрастанию
У - С - С - Р - П - О - М - Л - И - И - И
Из предложенной расстановки видим только возможные пары "УС" и "ЛИ" из начального слова, а все остальные по одной букве. Потому так и разрезаем считая с начала слова по одной букве и 2 раза по две.
Посчитаем, получим 8 разрезов.
Запишем это слово и мы
СИРИУСОЛИМП
После пояснения в условии о старшинстве букв, мы при одном разрезе имеем ситуацию, когда старшая из всех данных нам буква - «У».
Именно с ней в начале будет слово. Отрезаем прямо перед ней и отрезки переставляем.
Получаем слово
Теперь рассмотрим ситуацию как бы при двух разрезах.
Получаем такие слова-части:
Ну а если разрежем 4 раза, то разрежем на «УС» и первую букву «С». И переставим их вот так:
А теперь надо вспомнить алфавит в обратном порядке. Не а,б, в....и так далее, а наоборот, с максимально старшей буквы
Я замечаю только две возможные пары «УС» и «ЛИ» из того начального слова, что придумал Даниил. Ну а все остальные получаются только по одной букве. Разрезов будет по одной букве и только два раза по две буквы.
Итого: 8 разрезов .
Задание несложное. Важно вспомнить алфавит и понять, что чем дальше буква от начала алфавита, тем больше будет слово, которое с этой буквы начинается.
1) Для одного разреза нам нужно выбрать только одну, самая "большая" буква в слове СИРИУСОЛИМП - это буква У, перед ней и сделаем разрез, поменяем части местами. И получим слово УСОЛИМПСИРИ.
2) Теперь делаем два разреза. Нужно выбрать две наиболее "больших" буквы. Это так же будет У и С. Делаем разрезы. У нас тут две С. Самый "выгодный" вариант - чтобы они шли подряд. Тогда получаем три части: УС, СИРИ, ОЛИМП. Переставляем местами: УССИРИОЛИМП.
3) Если можно сделать три разреза, то отделим вторую С от И, чтобы потом у нас было О. Тогда получим слово: УССОЛИМПИРИ.
4) Чтобы слово получилось наибольшим, нужно, чтобы буквы шли в порядке, обратном алфавиту, то есть алфавит с конца. Тогда должно получиться слово: УССРПОМЛИИИ. Отрезаем УС (2 разреза), С (1 разрез), Р (2 разреза), П (1 разрез), О (1 разрез, второй мы уже сделали), М (1 разрез, второй уже сделали), Л - не делаем разрез, оставляем с буквой И. Оставшиеся две буквы И уже отрезаны, разрезы больше делать не нужно. Получаем:
2 + 1 + 2 + 1 + 1 + 1 = 8 разрезов.
ВКонтакте