Fişierul intrare/ieşire:pioni.in, pioni.outSursăStelele Informaticii 2007-2008, Clasele 11-12
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pioni

Nargy si Fumeanu joaca un joc pe un graf orientat aciclic cu N noduri si M muchii. In acest graf exista K pioni in noduri. Fiecare jucator poate muta, cand ii vine randul, oricati pioni din nodurile lor in noduri adiacente. Cel care nu mai poate muta atunci cand ii vine randul pierde partida. La inceputul unui joc, prima mutare o face jucatorul Nargy.
Dandu-se mai multe configuratii de pioni, sa se determine cine castiga jocul, daca ambii jucatori joaca optim.

Date de intrare

Fisierul de intrare pioni.in contine pe prima linie numerele T N M separate prin spatii. Urmatoarele M linii vor contine cate doua numere naturale a b cu semnificatia ca exista muchie de la a la b. Urmatoarele T linii vor descrie configuratii de pioni astfel: primul numar din linie va fi K si va fi urmat de inca K numere naturale reprezentand nodurile in care se afla pioni.

Date de iesire

In fisierul de iesire pioni.out se vor scrie urmatoarele pentru fiecare din cele T configuratii:

  • numele jucatorului care castiga pe o linie (Nargy sau Fumeanu)
  • daca Nargy poate castiga se va descrie si o prima mutare pe care o poate face astfel incat sa castige: se va scrie nr reprezentand numarul de pioni pe care ii muta la prima mutare, urmat de nr perechi de numere a b cu semnificatia ca se muta un pion din nodul a in nodul b

Restrictii

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 20.000
  • 1 ≤ M ≤ 50.000
  • 1 ≤ K ≤ 30.000
  • Pot exista mai multi pioni in acelasi nod

Exemplu

pioni.inpioni.out
2 4 3
2 1
3 1
4 3
3 2 2 3
2 1 4
Nargy
3 2 1 2 1 3 1
Fumeanu

Explicatie

In prima configuratie Nargy poate castiga mutand toti pionii din 2 si 3 in 1. Astfel, Fumeanu nu va mai putea muta.
In a doua configuratie singurul pion care se poate muta este cel din 4 (1 nu are noduri adiacente). Asadar, Nargy este fortat sa mute din 4 in 3, Fumeanu va muta apoi din 3 in 1, iar Nargy va pierde.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content