Masala #0684

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 9 %
4.3 (Baholar 7)
14

  

Kesishmalar #1

1 dan 2n2n gacha raqamlangan nuqtalar aylana atrofida soat strelkasi bo’ylab joylashgan. Nuqtalarning aniq nn tasi qora, nn tasi oq.
Quyidagi shartlarni qanoatlantiruvchi nn 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 nn 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 nn soni (1n105)(1 ≤ n ≤ 10^5). Ikkinchi qatorda uzunligi 2n2n bo’lgan B va W harflaridan iborat SS satr beriladi, satrning ii-belgisi(1i2n)(1 ≤ i ≤ 2n) B bo’lsa, ii- nuqta qoraligini, W bo’lsa oqligini bildiradi.

1-subtask(9 ball) Aylanada dastlab nn ta qora nuqta, so’ng nn ta oq nuqta joylashgan, n100n ≤ 100
2-subtask(15 ball): n8n ≤ 8.
3-subtask(31 ball): n300n ≤ 300.
4-subtask(45 ball): n105n ≤ 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.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin