tj

Tom & Jerry

== include(page="template/taskheader" task_id="tj") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| tj.in | tj.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="tj") ==

==Include(page="template/taskheader" task_id="tj")==
==Include(page="template/raw")==
 
tj
 
 
 
Tom & Jerry joaca un joc intr-un graf neorientat cu N noduri (numerotate de la 1 la N).
 
Tom alege unul dintre nodurile grafului si se pozitioneaza in acest nod. Apoi Jerry alege si el unul dintre nodurile grafului (eventual acelasi) si se pozitioneaza in acel nod.
 
Dupa aceste pozitionari "strategice", incepe jocul efectiv. Tom & Jerry efectueaza mutari alternativ. La fiecare mutare, ei se pot deplasa din nodul in care se afla in orice alt nod invecinat (doua noduri sunt invecinate daca exista o muchie intre ele) sau pot ramane pe loc (in acelasi nod).
 
Tom este cel care efectueaza prima mutare si scopul lui este de a-l prinde pe Jerry. Astfel, Tom castiga jocul daca ajunge in acelasi nod al grafului ca si Jerry. Jerry castiga jocul daca poate sa fuga de Tom la infinit (adica orice mutare ar efectua Tom, la orice moment, Jerry poate efectua la randul lui o mutare prin care sa evite sa ajunga in aceeasi pozitie ca si Tom).
 
h2. Cerinta
 
Pentru un graf dat, determinati daca Tom are strategie sigura de castig.
 
h2. Date de Intrare
 
Prima linie a fisierului tj.in contine numarul natural T, reprezentand numarul de grafuri descrise in continuare. Un graf este descris pe o succesiune de linii din fisierul de intrare, dupa cum urmeaza. Prima linie contine numerele naturale N si M reprezentand numarul de noduri, respectiv numarul de muchii ale grafului. Fiecare dintre urmatoarele M linii contine cate 2 numere naturale a si b, avand semnificatia ca exista muchie intre nodurile a si b. Intre descrierile a doua grafuri consecutive din fisierul de intrare se afla o linie goala.
 
h2. Date de Iesire
 
In fisierul de iesire tj.out veti afisa pentru fiecare graf din fisierul de intrare (in ordinea in care sunt descrise grafurile in fisier) "DA" (fara ghilimele), in caz ca Tom are strategie sigura de castig, respectiv "NU" (tot fara ghilimele), in caz contrar.
 
h2. Restrictii si precizari
 
S 1 -L- T -L- 20
 
S 1 -L- N -L- 256
 
S 0 -L- M -L- N*(N-1)/2
 
S Nu exista muchie de la un nod la el insusi.
 
S Intre doua noduri ale grafului exista cel mult o muchie.
 
S Cel putin 60% din teste vor avea N -L- 64
 
 
 
Exemple
 
tj.in tj.out
6 NU
 
2 0 DA
 
DA
 
4 4 DA
 
1 2 DA
 
1 3 NU
 
2 3
 
3 4
 
 
 
3 2
 
1 2
 
2 3
 
 
 
2 1
 
1 2
 
 
 
1 0
 
 
 
4 4
 
1 2
 
2 3
 
3 4
 
4 1
==Include(page="template/taskfooter" task_id="tj")==