|
Titlul: 077 Tom & Jerry Scris de: Mircea Pasoi din Iulie 10, 2005, 23:41:14 Aici puteţi discuta despre problema Tom & Jerry (http://infoarena.ro/problema/tj).
Titlul: Răspuns: 077 Tom & Jerry Scris de: VladS din Noiembrie 17, 2005, 20:41:14 Se poate face ceva cu cicluri ?
Eu ma gandeam la ceva de genu: Daca graful are un ciclu cu cel putin 4 noduri sau nu e conex afiseaza "NU". Altfel afiseaza "DA". Partea nasoala e ca a mers doar pe testul din enunt iar eu nu gasesc nici un contraexemplu. Titlul: Răspuns: 077 Tom & Jerry Scris de: Tiberiu-Lucian Florea din Noiembrie 17, 2005, 21:06:20 Dupa cum spuneam... o problema trebuie rezolvata constructiv in loc sa iei diverse idei de rezolvare si sa le cauti contraexemple. In orice caz, e greu de scos, cauta dismantlable graphs pe google.
Titlul: Răspuns: 077 Tom & Jerry Scris de: VladS din Noiembrie 18, 2005, 19:21:42 Am gasit cateva documente despre dismantlable graphs numai ca in ele nu prea se face referire la verificarea daca un graf este dismantible. Singurul algoritm care l-am gasit:
Cat timp graful are mai mult de un nod 1) Cauta doua noduri i si j astfel incat N(i) inclus in N(j) 2) Daca s-a gasit o astfel de pereche elimina nodul i din graf si continua altfel graful nu este dismantible Daca a ramas un nod graful e dismantible Am implementat numai ca nu prea merge (WA la greu). Algoritmul e bun sau am eu greseli de implementare ? Titlul: Răspuns: 077 Tom & Jerry Scris de: Filip Cristian Buruiana din Noiembrie 18, 2005, 21:44:46 Citat Eu ma gandeam la ceva de genu: Daca graful are un ciclu cu cel putin 4 noduri sau nu e conex afiseaza "NU". Altfel afiseaza "DA". Partea nasoala e ca a mers doar pe testul din enunt iar eu nu gasesc nici un contraexemplu. Un contraexemplu nu e chiar greu de gasit: Cod: 6 9 Tom se plaseaza in 1, Jerry neaparat in 4. Tom vine in 5 si oriunde muta Jerry el pierde ( si in graf exista si un ciclu de 5, si un ciclu de 4 ). Pentru a nu avea TOM strategie, ma gandeam ca ar trebui sa existe un ciclu in care fiecare nod sa nu apartina unui alt ciclu de lungime 3... Si altceva: ma gandeam sa construiesc ceva cu toate starile posibile ( sa avem un arbore curent de solutii si sa "expandam" cazurile ulterioare din fiecare nod ). Cred k ar trebui sa ma uit si eu pe Google k nu prea mi-a iesit implementarea ( desi nu pare ceva deosebit... ) [-( |