Fişierul intrare/ieşire:fantasy.in, fantasy.outSursăAlgoritmiada 2017, Runda 1
AutorAdrian Budau, Eugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fantasy

Acum mulţi mulţi ani in Regatul cel Mare din Cluj trăiau un vrăjitor vestit, un dragon si un cavaler cu o sabie fermecată într-un echilbru care era gata gata să dispară. Cei trei nu se înţelegeau deloc, însa niciunul nu era suficient de puternic incat să scape de ceilalţi doi. Astfel vrăjitorul putea la orice moment să isi folosească magia să omoare cavalerul. Cavalerul la rândul lui putea oricând cu o lovitură a sabiei sale fermecate să omoare dragonul, iar dragonul fiind complet imun la magia vrăjitorului putea oricând să îl manance.
Niciunul din cei trei nu se risca să-l inlăture pe cel pe care îl putea învinge deoarece ar fi fost neputincios împotriva celui rămas. De exemplu dacă vrajitorul ar fi încercat să scape de cavaler, dragonul ar fi putut scăpa de el.

Într-o zi însa vrajitorul, din noroc (sau poate din ghinion) a reuşit sa se teleporteze pe el insusi, pe dragon si pe cavaler într-un labirit sub forma unui arbore (graf neorientat conex aciclic), unde camerele labirintului reprezintă nodurile arborelui, iar o legatură între doua camere reprezintă o muchie din arbore.

Din acel moment, în fiecare secundă, fiecare dintre cele trei personaje fie s-a deplasat într-o celula adiacentă cu celula în care s-a aflat în secunda anterioara, fie a rămas pe loc. Daca la un moment dat doua din cele trei personaje se întalnesc, atunci cel mai puternic dintre cei doi îl omoară instantaneu pe celalalt, indiferent daca se întalnesc într-o cameră sau pe o legătură.

Astfel:

  • Dragonul în fiecare secundă se deplasa în camera cea mai apropiată de vrăjitor pentru a-l mânca
  • Cavalerul în fiecare secunda se deplasa în camera cea mai apropiata de dragon pentru a-l omorî. Daca dragonul era deja mort, el nu se va mai deplasa deloc pentru că vrăjitorul oricum îl va prinde şi îl va învinge.
  • Vrăjitorul observănd cum se deplasează dragonul si cavalerul şi-a construit cea mai bună strategie pentru ca la final doar el să mai fie în viata.

Din păcate vrăjitorul oricăt era de deştept, nu se pricepea la arbori aşa ca vă roagă să-i spuneţi cât mai repede dacă poate fi singurul supravieţuitor de la final, pentru ca în caz contrar să încerce să se teleporteze afară din labirint.

Date de intrare

Fişierul de intrare fantasy.in va conţine pe prima linie valorea T reprezentand numarul de teste din fisier. Un test are urmatoarea structura:

Pe prima sa linie exista 4 numere naturale N, D, C, V reprezentănd numărul de camere din labirint, respectiv indicii camerelor în care se află Dragonul(D), Cavalerul( C) şi respectiv Vrăjitorul(V).
Următoarele N - 1 linii vor conţine câte două valori fiecare x si y cu semnificaţia ca exista o legătura între camerele cu indicii x si y.
Aceste N - 1 legături vor descrie un arbore.

Date de ieşire

În fişierul de ieşire fantasy.out trebuie să se afle pe prima şi singura linie "DA"(Ghilimelele sunt doar pentru claritate) dacă vrăjitorul are o şansa sa fie singurul supravieţuitor la final, sau "NU" în caz contrar.

Restricţii

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 1.000
  • 1 ≤ D, C, V, x, y ≤ N
  • D ≠ C, D ≠ V, C ≠ V
  • Dragonul, Cavalerul şi Vrăjitorul se mută deodata în labirint
  • Daca cei 3 se întălnesc în acelaşi nod în aceeaşi secundă, atunci toţi 3 vor muri
  • Pentru teste in valoare de 30 de puncte 1 ≤ N ≤ 200 si 1 ≤ T ≤ 30.

Exemplu

fantasy.infantasy.out
3
4 2 4 3
1 3
2 3
3 4
4 3 4 1
1 2
2 3
3 4
3 1 3 2
1 2
2 3
DA
NU
NU

Explicaţie

În primul exemplu, vrăjitorul este prins între dragon şi cavaler însa observă că se poate muta în camera 1. Astfel după o secunda dragonul şi cavalerul se întalnesc in camera 2 unde cavalerul îl va doborî pe dragon. Din aces moment cavalerul nu mai are nicio şansa (deoarece a rămas doar cu vrăjitorul), iar vrăjitorul cu siguranţă va fi singurul rămas in viaţa la final.

în al doilea exemplu, vrăjitorul orice ar face va prins de câtre dragon orice ar face,

În al treilea exemplu, vrăjitorul este prins între cei doi si poate alege fie sa se deplaseze spre cavaler, omorăndu-l si rămanand singur cu dragonul, sau să ramană pe loc şi toţi 3 vor fi în acelaşi nod şi vor pieri.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?