C. Анаграм

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт input.txt

гаралт стандарт гаралт

Хэрэв $x$ тэмдэгт мөрийн үсгүүдийн байрыг солих замаар $y$ тэмдэгт мөрийг гаргаж чаддаг бол $x$-ийг $y$-ийн АНАГРАМ гэнэ. Жишээ нь "DOG" ба "GOD" нь харилцан анаграм, "BABA" ба "AABB" нь мөн харилцан анаграм, гэхдээ "ABBAC" ба "CAABA" нь биш юм.

Чамд $s$ ба $t$ гэсэн ижил урттай Англи цагаан толгой том үсгүүдээс тогтох тэмдэгт мөрүүд өгөгдсөн. Чи $s$ тэмдэгт мөрийг ашиглан $t$ тэмдэгт мөртэй анаграм тэмдэгт мөрийг гаргаж авах ёстой. Чамд $s$ тэмдэгт мөрийн дурын тэмдэгтийг дурын тэмдэгтээр солих үйлдэл зөвшөөрөгдсөн. Хамгийн цөөндөө хэдэн үйлдэл хийж $t$ тэмдэгт мөрийн анаграмыг гаргаж чадах вэ. Хэрэв хамгийн цөөн үйлдлээр олон янзын $t$-ийн анаграмыг гаргаж авч чаддаг бол тэдгээрийн толь бичгийн эрэмбээрх хамгийн багыг нь ол.

Толь бичгийн эрэмбэ гэдэг нь: $n$ урттай $p$ ба $q$ тэмдэгт мөрүүдийн хувьд хэрэв $p_{1} = q_{1}$, $p_{2} = q_{2}$, ... , $p_{k - 1} = q_{k - 1}$, $p_{k} < q_{k}$ байхаар $k$ ($1 ≤ k ≤ n$) дугаар олддог бол $p$ нь толь бичгийн эрэмбээр $q$-ээс бага юм. Энд тэмдэгт мөрийн тэмдэгтүүд $1$-ээс эхлэн дугаарлагдсан байна. Тэмдэгтүүд нь цагаан толгойн дарааллаар эрэмбэлэгдэнэ.

Оролт

Оролт хоёр мөрөөс тогтоно. Эхний мөрөнд $s$ тэмдэгт мөр, дараагийн мөрөнд $t$ тэмдэгт мөр байна. Тэмдэгт мөрүүдийн урт ижил буюу $1$-ээс $10^{5}$-н хооронд урттай байх ба Англи цагаан толгойн том үсгээс тогтно.

Гаралт

Эхний мөрөнд хийгдэх үйлдлийн хамгийн бага тоо болох $z$-ийг хэвлэ. Дараагийн мөрөнд $z$ үйлдлээр гарч болох толь бичгийн эрэмбээрх хамгийн бага анаграмыг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
ABA
CBA
Гаралт
1
ABC
Оролт
CDBABC
ADCABD
Гаралт
2
ADBADC

Тэмдэглэл

Хоёр дахь жишээнд $2$ үйлдлийн дараа $t$-ийн найман анаграм гарч ирэх боломжтой: "ADBADC", "ADDABC", "CDAABD", "CDBAAD", "CDBADA", "CDDABA", "DDAABC", "DDBAAC". Эдгээр нь толь бичгийн эрэмбээрээ бичигдсэн ба хамгийн бага нь "ADBADC" юм.

Сэтгэгдлүүдийг ачааллаж байна...