Miruna are N
cartonase pe care le-a asezat in linie dreapta pe masa. Fiecare cartonas are
o fata colorata cu rosu, iar cealalta cu albastru.
Miruna si fratiorul ei se gandesc la urmatorul joc:
- O mutare valida consta din alegerea unui cartonas cu fata rosie in sus si
intoarcerea lui. In plus, daca doreste, cel care e la mutare poate sa isi aleaga
orice alt cartonas (indiferent de culoarea fetei care este in sus) care se afla
la stanga celui ales initial si sa il intoarca.
- Cei doi copii efectueaza alternativ mutari valide.
- Castiga cel care efectueaza ultima mutare.
- Intotdeauna Miruna este cea care efectueaza prima mutare.
Cerinta
Stiind ca cei doi copii
vor juca optim, se cere sa se stabileasca castigatorul pentru o configuratie
data a cartonaselor.
Date de intrare
Pe prima linie a fisierului
de intrare cartonase.in se gaseste
un numar intreg T, reprezentand
numarul de seturi de date de test ce vor urma. Pe fiecare dintre urmatoarele
T linii se va afla un numar intreg
N, urmat de un spatiu, apoi de
N caractere despartite prin cate
un spatiu ce pot fi R sau A,
semnificand culorile fetelor cartonaselor care sunt in sus.
Date de iesire
Fisierul cartonase.out
va contine T linii. Pe linia
i (1<=i<=T)
va fi scris mesajul DA in cazul
in care Miruna este cea care castiga jocul descris pe linia i+1
in fisierul de intrare, respectiv mesajul NU
in caz contrar.