Masala #0684
Kesishmalar #1
1 dan gacha raqamlangan nuqtalar aylana atrofida soat strelkasi bo’ylab joylashgan. Nuqtalarning aniq tasi qora, tasi oq.
Quyidagi shartlarni qanoatlantiruvchi 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 ta kesmani chizish orqali maksimal kesishish koeffitsientiga erishishdan iborat. Kesishish koeffitsienti bir biri bilan kesishadigan kesmalar juftliklari soniga teng.
Birinchi qatorda bitta butun soni . Ikkinchi qatorda uzunligi bo’lgan B va W harflaridan iborat satr beriladi, satrning -belgisi B bo’lsa, - nuqta qoraligini, W bo’lsa oqligini bildiradi.
1-subtask(9 ball) Aylanada dastlab ta qora nuqta, so’ng ta oq nuqta joylashgan,
2-subtask(15 ball): .
3-subtask(31 ball): .
4-subtask(45 ball): .
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.