Masala #QOYHDVMPUU
Bir o'lchovli labirint
Dilshod xonalari \(1\) dan \(n\) gacha raqamlangan bir o'lchovli labirintda adashib qoldi. Hozirda u labirintning \(k\)-xonasida turibdi va labirindan chiqish uchun \(1\)-yoki \(n\)-xonalardan biriga borishi kerak . Dilshod o'z istagi bilan yura olmaydi, shuning uchun ham turgan xonasining belgisilga qarab yuradi.
- \(L\) belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni chap xonaga o'ta oladi.
- \(R\) belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni o'ng xonaga o'ta oladi.
Harakat qilishni boshlashdan oldin, Dilshod istalgan xonalarining belgilarini almashtira oladi. U minimal nechta almashtirishlar yordamida labirintdan chiqib keta oladi?
Birinchi qatorda bitta butun son - \(T\) testlar soni kiritiladi.
Keyingi qatordan boshlab har bir test uchun alohida, birinchi qatorda \(n(1 \leq n \leq 2 * 10^5)\)labirintdagi xonalar soni va \(k(1 < k < n)\) hozirda Dilshod turgan xonaning tartib raqami kiritiladi. Ikkinchi qatorda esa bitta satr, labirintdagi xonalarning belgilar kiritiladi.
Barcha testlar kesimida \(n\)larning yig'indisi \(10^6\) dan oshmaydi.
Har bir test uchun alohida qatorda, DIlshod minimal nechta o'zgartirishlar yordamida labirintdan chiqib ketishini toping.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 6 3 RLRRLR 4 2 LLRR 8 4 LRLRRLLL |
1 0 2 |
1-testda, Dilshod labirintning 3-xonasid turibdi. 1 ta belgini o'zgartirish yordamida labirintni RLLRLR ko'rinishiga olib keladi.
So'ng quyidagicha harakat qiladi: RLLRLR → RLLRLR → RLLRL
1-raqamli xonaga kelib bo'lgach, Labirintdan chiqib ketadi.
2-testda faqat chapga yurgan holda labirintdan chiqib ketadi.
3-testda esa Dilshod oldin satrni LRLRRRRL ga o'zgartiradi.
So'ng quyidagicha harakat qiladi: LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL. Oxirgi xonaga kelgach, labirintdan chiqib ketadi.
Telegram kanalimizga obuna bo'ling