Muallif: __thecrash__
G. Shokolad fabrikasi
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Katta shokolad fabrikasida yangi konveyer liniyasi ishga tushirildi. Lentada qator holda \(2 \times n-1\) ta shokolad bo'lagi joylashgan bo'lib, ularning har biri yo achchiq shokolad yoki sutli shokolad turidan biri hisoblanadi.
Fabrika barcha shokoladlarning turini va tartibini allaqachon belgilab qo'ygan. Shokoladlar turi uzunligi \(2 \times n-1\) bo'lgan \(s\) satri orqali beriladi: \(1 \le i \le 2 \times n-1\) uchun, agar \(s_i = \text{'D'}\) bo'lsa, \(i\)-bo'lak achchiq shokolad, agar \(s_i = \text{'M'}\) bo'lsa, \(i\)-bo'lak sutli shokolad hisoblanadi.
Nazoratga jami \(n\) nafar sifat nazorati inspektori jalb qilingan bo'lib, ular \(1\) dan \(n\) gacha raqamlangan. Har bir \(j\)-inspektor ketma-ket joylashgan bo'laklarni, ya'ni \(a_j, a_j+1, \dots, b_j\) pozitsiyalaridagi bo'laklarni tekshirmoqchi, bunda \(1 \le a_j \le b_j \le 2 \times n-1\). Bundan tashqari:
- har bir inspektor kamida \(n\) ta shokolad tekshirishi kerak, ya'ni \(b_j - a_j + 1 \ge n\);
- hech qanday ikkita inspektor aynan bir xil bo'laklarni tekshirmasligi kerak: \(j \neq k\) bo'lsa, \(a_j \neq a_k\) yoki \(b_j \neq b_k\).
Sutli shokolad tarkibidagi sut mahsuloti tufayli saqlash va harorat nazorati talablari ancha qattiqroq, shuning uchun rahbariyat barcha inspektorlar bir xil miqdordagi sutli shokolad bo'lagini tekshirishini xohlaydi — bu nazoratni adolatli taqsimlash uchun ham muhim.
Rahbariyatga yordam bering: shunday \(x\) (\(0 \le x \le 2 \times n-1\)) sonini toping, unda har bir inspektor aynan \(x\) ta sutli shokolad tekshiradigan qilib intervallarni taqsimlash mumkin bo'lsin. Bunday \(x\) doimo mavjud.
Kiruvchi ma'lumotlar
Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) — bunda \(2 \times n-1\) shokolad bo'laklari soni, \(n\) esa inspektorlar soni. Ikkinchi qatorda uzunligi \(2 \times n-1\) bo'lgan \(s\) satri: \(i\)-bo'lak achchiq bo'lsa 'D', sutli bo'lsa 'M'.
Chiquvchi ma'lumotlar
Har bir inspektor tekshiradigan sutli shokoladlar sonini — \(x\) ni chop eting. Bir nechta yechim bo'lsa, istalganini chiqarish mumkin.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
3 MDMDM |
2 |
2 |
1 D |
0 |
Izoh
Birinchi namunada \(3\) ta inspektor va \(2 \times 3 - 1 = 5\) ta bo'lak bor. Har biri aynan \(2\) ta sutli shokolad tekshiradigan intervallarga misol: \([1,3]\), \([1,4]\), \([2,5]\) — barchasi kamida \(3\) ta bo'lakdan iborat va bir-biridan farqli.
Ikkinchi namunada \(1\) ta inspektor va \(1\) ta bo'lak bor. Yagona mumkin bo'lgan interval \([1,1]\), bu \(x = 0\) ni beradi.