E — Tánc a sakktáblán

Egy vidámpark évfordulós ünnepségét szervező csoport meghívott egy prominens tánctársulatot, hogy adjanak elő tematikus táncokat az ünnepségen. A társulat négy táncot készített elő sakk témában, amelyeket ennek megfelelően Király, Huszár, Futár, illetve Bástya előadásnak neveztek el.

Mindegyik táncot valahány tánccsoport adja elő. A vidámparkbeli szokatlan helyszín azonban nehézséget okoz néhány érzékeny társulati tagnak. A társulat fő koreográfusa szerint ha egy táncos az előadás közben látja a saját csoporttársát, az összezavarhatja őt, és tévesen a társa mozdulatait kezdheti el utánozni. Következésképpen az egy csoporthoz tartozó táncosokat megfelelően szét kell szórni a tánctéren, hogy más csoportok tagjai kitakarják őket egymás elől. Az így kapott elrendezés ráadásul nem vihető át a többi előadásra, mivel az egyes előadások stílusa és mozdulatai nagymértékben különböznek egymástól.

A szervezőknek végül sikerült formalizálni a pontos peremfeltételeket a négy tánc mindegyikéhez a társulat igényei alapján:

Az előadásra egy szabályos S × S méretű négyzetrácson kerül sor, ahol a rácspontok padlóra festett jelek.

Minden táncos egy jelet foglal el, egyetlen jel sem marad üresen, egy jelen mindig csak egy táncos áll, és minden táncos ugyanazt a jelet foglalja el a teljes előadás alatt. Minden táncos pontosan egy csoporthoz tartozik.

Az egyes jelek középpontjai egy Descartes-féle koordináta-rendszer egész koordinátájú pontjai. Bármely jel középpontjának és a legközelebbi szomszédos jel középpontjának a távolsága 1.

Legyen A és B két különböző jel, amelyek középpontjai legyenek rendre az (x₁, y₁) és az (x₂, y₂) koordinátákon!

• A Király előadáson: ha |x₁ – x₂| < 2 és |y₁ – y₂| < 2, akkor A-t és B-t különböző csoportok tagjainak kell elfoglalnia.
• A Huszár előadáson: ha |x₁ – x₂| · |y₁ – y₂| = 2, akkor A-t és B-t különböző csoportok tagjainak kell elfoglalnia.
• A Futár előadáson: ha |x₁ – x₂| = |y₁ – y₂|, akkor A-t és B-t különböző csoportok tagjainak kell elfoglalnia.
• A Bástya előadáson: ha |x₁ – x₂| · |y₁ – y₂| = 0, akkor A-t és B-t különböző csoportok tagjainak kell elfoglalnia.

A szervezők mind a négy tánc esetén tudni szeretnék, hogy minimálisan hány csoportra van szükség a tánc előadásához.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egyetlen sorból áll, amelyben egy S egész szám, egy szóköz, valamint a 'K', 'N', 'B' és 'R' nagybetűk egyike szerepel. S a jeleket tartalmazó rács méretét adja meg (1 ≤ S ≤ 1000), a betűk pedig rendre a Király (King) előadást, a Huszár (Knight) előadást, a Futár (Bishop) előadást, illetve a Bástya (Rook) előadást szimbolizálják.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni a megadott méretű jelrácson a megadott tánc előadásához szükséges csoportok minimális számával.

Példa bemenet

1. 2 N
2. 8 R
3. 2 B
4. 1 K

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 1
2. 8
3. 2
4. 1

letöltés szöveges állományként