Masala #0687

Xotira 16 MB Vaqt 1000 ms
14

Kesishmalar #4

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.


Kiruvchi ma'lumotlar:

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\).


Chiquvchi ma'lumotlar:

Bitta butun son - masalaning javobini chiqaring.


Misollar
# input.txt output.txt
1
3
BBWWBW
2
2
5
BWBWBBWBWW
8
Izoh:

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.