038 Dans

[•Teodor94]

Aici puteti discuta despre problema Dans.

[•UTCN_Crisan_Marginean_Soucup]

Testele contin grafuri care au un ciclu eulerian?

[•gabrielinelus]

Salut, m-am chinuit cu problema asta ceva mai mult timp   si am ajuns la concluzia ca ori eu nu inteleg bine ceva ori enuntul e gresit. In enunt scrie foarte frumos :  

"De asemenea, din motive de eficienţă, în momentul finzalizării unui dans, în ring trebuie să >> rămână un singur dansator << din perechea curentă şi >> să urce doar un singur alt dansator << (cei doi dansatori fiind bineînţeles compatibili). În plus, acelaşi dansator poate dansa maxim două dansuri consecutive (evident, trei dansuri ar fi epuizante)."


 Eu de aici inteleg ca practic e un lant euler / ciclu euler adica ceva conex   . Poate gresesc ... ( astept pareri   ).
Am o sursa demonstrativa :
http://www.infoarena.ro/job_detail/1219698 aici verific conexitatea si iau 0
http://www.infoarena.ro/job_detail/1219699 aici nu o verific si iau 100

Partea a doua suna asa: Bun sa zicem ca problema e facuta sa fie asa mai multe cicluri / lanturi ... dar atunci de ce sunt doar 2 noduri cu grad impar de ce nu 4 6 8 ... 200 si sa scot 2 .. 3 .. 4 .. 100 lanturi  si de ce nu si vreo 3-4 cicluri ? Si totusi pentru 100 merge sa scot: doar un ciclu sau un lant, dar mai exista si varianta in care scot un ciclu dar mai sunt alte N cicluri care nu au legatura cu cel scos ( cicluri pe care nu le scot ) sau un lant si mai exista alte cicluri care nu au legatura cu lantul scos ( pe care iar nu le scot ) ? Dubios... ( zic eu ).

[•klamathix]

Nu știu cum sunt făcute testele, dar nu e corect să verifici dacă e conex în sensul clasic. Dacă ai o componentă conexă și un nod izolat e perfect ok dacă componenta are soluție. Ca să răspunzi NU trebuie să existe cel puțin două componente conexe care conțin muchii.

[•gabrielinelus]

Mersi de raspuns, uite am incercat sa fac verificarea asa cum m-ai sfatuit.

1) am marcat care noduri apar sa aiba muchii ( deci nu sunt izolate )
2) am facut un DFS din noduri care NU sunt izolate
3) am verificat daca un nod nu apartie componentei conexe respective si NU este un nod izolat

Rezultatul este tot 0 puncte:

http://www.infoarena.ro/job_detail/1219706?action=view-source

Astept raspuns 

[•klamathix]

Ok, am investigat putin. Exista intr-adevar teste cu noduri izolate, dar nu exista teste cu 2 componente care contin muchii. Motivul pentru care tu iei 0 in continuare e fiindca nu resetezi used-ul tot timpul si apare-ul deloc. Le-am initializat cu 0 la inceputul testului si am luat 100 cu sursa la care mi-ai dat link.

[•gapdan]

Ma poate ajuta si pe mine cineva? Pur si simplu nu stiu ce gresesc      Am facut ciclu eulerian dintr-un nod cu grad impar si afisam NU daca aveam mai mult de 2 noduri cu grad impar sau doar un singur nod cu grad impar...
http://www.infoarena.ro/job_detail/1240520?action=view-source