Fişierul intrare/ieşire:	petrick.in, petrick.out	Sursă	AGM 2019, runda nationala
Autor	Patrick Sava	Adăugată de	Patrick Sava •xtreme77
Timp execuţie pe test	0.005 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Petrick

Această problemă este numită Petrick - şi acest lucru nu trebuie confundat cu numele autorului. Petrick se referă la "trick", un sinonim pentru frazele româneşti "pe smecherie" sau "pe barosaneala". Trick-ul real se referă la a vedea dacă tu, un uimitor jucător de şah, poţi câştiga împotriva adversarului într-o singură mişcare (aminteste-ti că esti un talentat!).

În mod formal, ti se dă o tabla de şah fără pioni, cu N piese pe ea şi ti se cere să vezi dacă albul ii poate da sah-mat negrului prin mutarea unei singure piese. Reţine că starea tablei de şah poate fi generata într-un joc ipotetic de şah, în conformitate cu regulile bine cunoscute ale şahului.

Urmeaza o scurtă descriere a jocului de şah. Şahul este un joc jucat pe o tablă pătrată de 8 x 8, cu diferite piese. Piesele sunt regi, regine, nebuni, cai, sau ture. Fiecare piesă poate fi neagra sau alba, iar fiecare piesă se poate afla pe o singură celulă. Nu poate fi mai mult de o piesa intr-o celulă. Fiecare piesă poate, în funcţie de tipul său, să se deplaseze la alte celule; în special:

1. Regele se poate muta în orice celulă adiacenta (verticala, orizontala sau diagonala).
2. Tura poate să se deplaseze ortogonal în sus, în jos, în stânga sau în dreapta pe oricare distanţă, atâta timp cât nu "sare peste" alte piese.
3. Nebunul poate muta în diagonală pe orice distanţă, atâta timp cât nu "sare peste" alte piese.
4. Regina poate realiza orice mutare pe care un nebun sau o tura o pot face.
5. Calul se poate muta ortogonal în sus, în jos, în stânga sau în dreapta cu două celule, mutare urmată imediat de o mişcare suplimentară de o celula perpendiculare pe ultima (în forma literei mari L); calul poate "sări peste" alte piese.

Există exact un rege al fiecărei culori.
Există cel mult două ture, nebuni şi cai de fiecare culoare.
Dacă există doi nebuni de aceeaşi culoare, atunci se garantează ca suma paritatilor pozitiilor celulelor pe care acestia sunt situati este diferita.
O piesă nu se poate muta într-o celulă care conţine o piesa de aceeaşi culoare. Dacă o piesă se mişcă într-o celulă unde se afla o piesa de culoarea opusă, atunci piesa care se afla pe celula iniţiala este scoasă din joc.
Spunem că o culoare este în check (adica sah) dacă şi numai dacă o piesa de culoarea opusă s-ar putea muta în celula care conţine regele acelei culori. Nu este permis ca o piesa sa faca o mutare invalida.
Spunem că o culoare este în check-mate (sah-mat) dacă şi numai dacă este in check (sah) şi nu poate face mişcări valide.

Acum, este necesar să descoperi dacă albul poate face o mişcare valida care pune negrul în check-mate.

Date de intrare

Fişierul de intrare petrick.in va conţine N, numărul de piese. Următoarele N linii vor conţine fiecare câte un şir de caractere din setul {king, rook, queen, bishop, knight}, un şir de caractere din setul {black, white} şi două numere întregi din multimea {1, 2, 3, 4, 5, 6, 7, 8}, care indică poziţia piesei pe tablă. Primul şir indică tipul piesei, în timp ce al doilea indică care dintre jucătorii deţine piesa.

Date de ieşire

Fişierul de ieşire petrick.out trebuie să conţină un şir care descrie dacă vei câştiga în următoarea mişcare sau nu. Acest şir va fi Checkmate! dacă vei câştiga în următoarea mişcare sau Bad Luck! altfel.

Restricţii

• 1 ≤ N ≤ 16
• Limita de timp a acestei probleme a fost micsorata de la 1 secunda la 0.01 pentru a proteja evaluatorul.

Exemplu

Explicaţie

Exista cel putin o mutare care ii permite albului sa ii dea sah-mat negrului.

Cum se trimit solutii?