Fişierul intrare/ieşire:piese2.in, piese2.outSursăAlgoritmiada 2009, Runda 1
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.85 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Piese2

Miruna si Aglaia au primit de Mos Nicolae din partea parintilor un joc cu piese colorate. Acesta consta din K piese rosii, K piese albastre si o tabla de joc de dimensiune 1 x N. Regulile jocului sunt urmatoarele:

  • La inceput se pozitioneaza piesele pe tabla astfel incat sa nu existe 2 piese pe aceeasi coloana, iar oricare 2 piese consecutive sa fie colorate distinct. Prima piesa trebuie sa fie rosie.
  • Cele doua fetite vor efectua mutari alternativ, pana cand una dintre ele nu va mai putea efectua nicio mutare, moment in care ea va pierde jocul.
  • Miruna poate muta doar piese rosii, iar Aglaia doar piese albastre.
  • O mutare consta din alegerea unei piese si deplasarea ei o coloana spre dreapta sau spre stanga daca nu se paraseste tabla si daca respectiva locatie nu este ocupata de alta piesa.
  • Miruna este cea care efectueaza prima mutare.

Fetitele sunt foarte inteligente, asa ca ele vor juca intotdeauna optim. Pentru o configuratie initiala a pieselor, va trebui sa aflati cine va castiga jocul.

Date de intrare

Fişierul de intrare piese2.in contine pe prima linie 3 numere naturale T, N si K, reprezentand numarul de teste ce vor urma, dimensiunea tablei de joc, respectiv numarul de piese de o anumita culoare. Urmatoarele T linii vor contine cate 2 * K numere naturale. Acestea vor fi distincte si se vor da in ordine crescatoare. Ele vor reprezenta pozitiile initiale ale pieselor.

Date de ieşire

În fişierul de ieşire piese2.out veti afisa T linii, pe linia i aflandu-se numele fetitei castigatoare pentru jocul cu numarul i.

Restricţii

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 109
  • 1 ≤ K ≤ 105
  • 2*K ≤ N
  • Pentru 20% din teste N ≤ 10

Exemplu

piese2.inpiese2.out
2 4 1
1 3
1 4
Miruna
Aglaia

Explicaţie

Avem o tabla de lungime 4, si cate o piese din fiecare culoare. In primul joc Miruna muta pe 2, Aglaia muta pe 4, Miruna pe 3 si castiga. In al doilea joc Miruna muta pe 2, Aglaia pe 3, Miruna pe 1, Aglaia pe 2 si castiga.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content