АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Өгөгдсөн “А” string дээр дараах үйлдлүүдийг хийж болно.

1. reverse(A) – өгөгдсөн string – ын тонгорсон хувилбарыг гаргаж авна.

Жишээ нь: reverse(“abc”) = “cba”

1. shuffle(A) – үндсэн string -с гаргаж авсан дурын string

жишээ нь: shuffle(“god”) ϵ [‘god’, ‘gdo’, ‘ogd’, ‘odg’, ‘dgo’, ‘dog’]

1. merge(A1, A2) – A1 болон A2 -г нэгтгэх байдлаар гаргаж авсан дурын string. Ингэхдээ A1 болон A2 string – үүдийн тэмдэгтийн дарааллыг хадгалсан байна.

жишээ нь: A1 = “abc”, A2 = “def” гэвэл merge(A1, A2) – н боломжит утгууд нь

1. “abcdef”
2. “abdecf”
3. “adbecf” гэх мэтчилэн байж болно.

Дурын A string өгөгдөхөд “s” string -г дараах байдлаар гаргаж авч болно.

s ϵ merge(reverse(A), shuffle(A)). Тэгвэл, лексикографын хувьд хамгийн бага байх A string -г ол.

Жишээ нь: s = abab. Үүнийг бид 2 ширхэг ab string болгож хувааж болно. Энэ string – ын тонгорсон хувилбар нь ba бөгөөд abab – г гаргаж авахын тулд shuffle хийж болохуйц string – г олох хэрэгтэй.

2 талын a болон b тэмдэгтүүдийг орхивол голын 2 тэмдэгт нь reverse string – тэй адилхан болно. Бидний shuffle string нь ab байх хэрэгтэй.

Лексикографын хувьд ab < ba учир бидний хариулт нь ab болно.

Функцын тодорхойлолт

reverseShuffleMerge функцыг гүйцээж бич. Шаардлагад нийцэх, лексикографын хамгийн бага string -ыг буцаана.

Параметр:

s: оролтын string

Оролтын формат

1 мөр string.

Хязгаарлалт

s нь англи, жижиг үсгээс бүрдсэн байна. [a-z]

1<= |s| <= 10000

Гаралтын формат

Лексикографын хамгийн бага, зөв А string -г буцаана.

Жишээ оролт – 0

Eggegg

Жишээ гаралт – 0

egg

Тайлбар – 0

eggegg –ыг адилхан тэмдэгттэй байхаар дараах байдлаар хуваая. “egg”, “egg”

reverse(“egg”) = “gge”

shuffle(“egg”) -н үр дүн “egg” байж болно.

“eggegg” нь merge(“gge”, “egg”) -н үр дүн юм. Merge хийхээр: eggegg

‘egg’ < ‘gge’

Жишээ оролт 1

abcdefgabcdefg

Жишээ гаралт 1

agfedcb

Тайлбар 1

String -ыг адилхан тэмдэгттэй байхаар 2 string болгож хуваая. abcdefg болон abcdefg

Reverse(“abcdefg”) = gfedcba

Shuffle(“agfedcb) нь bcdefga байж болно.

Merge хийвэл abcdefgabcdefg

Жишээ оролт 2

aeiouuoiea

Жишээ гаралт 2

aeiou

Тайлбар 2

String -г Адилхан тэмдэгттэй байхаар хуваана: aeiou

Reverse(“aeiou”) = uoiea

Merge хийвэл aeiouuoiea

Орчуулсан Б.Баясгалантөгөлдөр АНУ