C. Палиндром өөрчлөлт

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

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

оролт стандарт оролт

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

Наам өөрийн компьютер дээр $n$ ширхэг Англи жижиг үсгээс бүрдсэн тэмдэгт мөрөөр тоглож байна. Энэ тэмдэгт мөр ямар ч утгагүй учраас Наам тэмдэгт мөрөө илүү сайхан болгохоор шийджээ. Үүний тулд тэр $4$ ширхэг сумтай товч (зүүн, баруун, дээш, доош) ашиглан тэмдэгт мөрөө палиндром болгох юм.

Одоо заагч сум тэмдэгт мөрийн ямар нэг тэмдэгтийг зааж байгаа бөгөөд энэ байрлалыг $i$-р ($1 ≤ i ≤ n$, тэмдэгт мөрийн тэмдэгтүүдийг нэгээс эхлэн дугаарлая) байрлал гэж бодъё. Зүүн эсвэл баруун сумтай товчийг ашиглан тэмдэгт мөрийн эргэн тойронд заагчийг шилжүүлнэ. Мөн тэмдэгт мөр эргэдэг: энэ нь Наам зүүн сумтай товчийг дарахад заагч сум $i > 1$ байрлалд эсвэл тэмдэгт мөрийн төгсгөлд (өөрөөр хэлбэл, $n$-р байрлал) байхаас бусад үед $i - 1$ байрлалд шилжинэ гэсэн утгатай. Баруун товч мөн ижил нөхцлөөр дарагдана ($i = n$ бол заагч тэмдэгт мөрийн эхэнд гарч ирнэ).

Наам дээшээ товчийг дарвал заагчийн зааж байгаа мөрийн үсгийг Англи цагаан толгойн дараагийн үсгээр өөрчлөх болно (цагаан толгойг мөн эргэдэг гэж үзнэ, өөрөөр хэлбэл '$z$'-н дараа '$a$' байна). Доошоо товч ижил нөхцлөөр дарагдана.

Эхлээд заагч сум мөрийн $p$-р байрлалд байна.

Наам үүнийг аль болох хурдан дуусгахыг хүсэж байгаа, учир нь хийх гэрийн даалгавар маш их байна. Тэмдэгт мөрийг палиндром болгоход хамгийн багадаа хэдэн сумтай товч дарахыг тооцоход та түүнд тусалж чадах уу?

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан хоёр бүхэл $n$ ($1 ≤ n ≤ 10^{5}$) ба $p$ ($1 ≤ p ≤ n$) тоог агуулна, эдгээр нь Наамын тэмдэгт мөрийн урт ба заагчийн анхны байрлал.

Дараагийн мөр нь Наамын тэмдэгт мөрийн $n$ ширхэг жижиг үсгүүдийг агуулна.

Гаралт

Тэмдэгт мөрийг палиндром болгож өөрчлөхөд хэрэгтэй хамгийн бага даралтын тоог хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
8 3
aeabcaez
Гаралт
6

Тэмдэглэл

Урдаасаа болон хойноосоо ижил уншигдаж байвал тэмдэгт мөрийг палиндром гэнэ.

Жишээнд Наамын анхны тэмдэгт мөр нь: (заагчийн байрлалыг тодоор тэмдэглэсэн).

Оновчтой шийд нь Наам дараах $6$ алхмуудыг хийж болно:

Үр дүнд нь , тэмдэгт мөр үүсэх ба энэ нь палиндром.

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