Masala #0685
Kesishmalar #2
1 dan \(2n\) gacha raqamlangan nuqtalar aylana atrofida soat strelkasi bo’ylab joylashgan. Nuqtalarning aniq \(n\) tasi qora, \(n\) tasi oq.
Quyidagi shartlarni qanoatlantiruvchi \(n\) ta kesma chizamiz:
- har bir kesma qaysidir oq va qaysidir qora nuqtalarni ulaydi.
- har bir nuqtaga ko’pi bilan bitta kesma ulanishi mumkin.
Sizning vazifangiz shu kabi \(n\) ta kesmani chizish orqali maksimal kesishish koeffitsientiga erishishdan iborat. Kesishish koeffitsienti bir biri bilan kesishadigan kesmalar juftliklari soniga teng.
Birinchi qatorda bitta butun \(n\) soni \((1 ≤ n ≤ 10^5)\). Ikkinchi qatorda uzunligi \(2n\) bo’lgan B va W harflaridan iborat \(S\) satr beriladi, satrning \(i\)-belgisi\((1 ≤ i ≤ 2n)\) B bo’lsa, \(i\)- nuqta qoraligini, W bo’lsa oqligini bildiradi.
1-subtask(9 ball) Aylanada dastlab \(n\) ta qora nuqta, so’ng \(n\) ta oq nuqta joylashgan, \(n ≤ 100\)
2-subtask(15 ball): \(n ≤ 8\).
3-subtask(31 ball): \(n ≤ 300\).
4-subtask(45 ball): \(n ≤ 10^5\).
Bitta butun son - masalaning javobini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 BBWWBW |
2 |
| 2 |
5 BWBWBBWBWW |
8 |
Birinchi misol uchun kesmalarni chap tomondagi rasmdagi kabi o’tqizadigan bo’lsak, kesishish koeffitsienti 2 bo’ladi. O’ng tomondagi rasmda esa, kesishmalar soni 3 ta bo’lishiga qaramay, 2- va 5- nuqtalardan o’tuvchi va 6- va 3- nuqtalardan o’tuvchi kesmalar masala shartiga to’g’ri kelmaydi, chunki kesmaning ikki tarafidagi nuqtalar oq va qora rangda bo’lishi lozim.
Telegram kanalimizga obuna bo'ling