e-olymp 332. Детская железная дорога

Витэк не прекращает своих игр с кубиками. А тут еще папа подарил ему детскую железную дорогу. Витэк расставляет какое-то количество кубиков по одному на вагончик и перед тем как закончить игру, решает перестроить состав таким образом, чтобы получившееся слово было лексикографически наименьшим из всех возможных, но так как он уже наигрался, поэтому может только один раз отцепить какое-то количество кубиков и паровозиком перевезти их в хвост своего состава.

Какое слово получится у Витэка?

Входные данные

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

Выходные данные

Слово, которое образовал Витэк.

Задача взята с сайта e-olymp.

Тесты

Входные данные Выходные данные
CBABC ABCCB
XXXXX XXXXX
ABEABFABBABC ABBABCABEABF
RATOBCQATOBC ATOBCQATOBCR
OROOXOOSTO OOROOXOOST
 LBDEAFAARDEABBAF AARDEABBAFLBDEAF

Алгоритм

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

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

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

Так как мы имеем право выбирать подслово только начиная от некоторого символа и до конца строки, то нам следует сравнить все подстроки начинающиеся с вхождения минимального символа и заканчивающиеся в конце слова.

Рассмотрим на произвольно выбранном примере:

                                                               LBDEAFAARDEABBAF                                                                                   

Тогда следует сравнить такие подслова:

AFAARDEABBA
     AARDEABBA
        ARDEABBA
                   ABBAF
                           A

Найти среди них минимальное лексикографическое и передвинуть его в начало слова.

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

  1. Прочитаем слово.
  2. Найдем минимальный символ в данном слове.
  3. Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF  и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
  4. Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF  и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
    Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
    Примечание: следует отметить, что даже без  выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
  5. И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
  6. После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

Код программы:

Код программы

Засчитанное решение

Related Images:

One thought on “e-olymp 332. Детская железная дорога

Добавить комментарий