Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament | Linkuri


Vizualizare solutie

Titlul problemei: caini
Numarul problemei: 1
Runda: Runda 2 - Concurs
Solutie: Asociem problemei un graf neorientat astfel:

multimea cainilor reprezinta multimea varfurilor grafului

exista muchie intre nodul a si nodul b daca cainii a si b se dusmanesc.

Vom reprezenta graful prin liste de adiacenta.

G[a][0]=numarul de caini cu care se dusmaneste cainele a

G[a][i]= al i -lea caine cu care se dusmaneste cainele a.

Numim configuratie o multime de caini aflati pe un anumit mal.

Mai exact o configuratie este o structura cu doua campuri:

mal care poate fi 0 sau 1

T care este vectorul caracteristic al multimii cainilor situati pe malul mal.

O astfel de reprezentare este costisitoare ca memorie, prin urmare, pentru a memora toate

configuratiile corecte vom reprezenta o configuratie condensat, ca un nr.

Putem considera vectorul caracteristic ca fiind reprezentarea binara a unui numar

si retinem numarul respectiv in baza 10, la care adaugam malul drept cea mai semnificativa cifra din reprezentare.

Pentru a utiliza toate configuratiile de caini valide (deci in care oricare doi caini nu se dusmanesc)

putem utiliza metoda backtracking sau un algoritm de tip succesor.

Configuratiile valide generate sunt retinute in forma condensata in vectorul c.

Pe parcursul generarii vom retine si max (numarul maxim de caini care nu se dusmanesc, deci

care pot fi lasati singuri pe acelasi mal.

Numarul minim de locuri este minloc=n-max+1 (daca putem gasi o schema de transport cu n-max+1 locuri in barca) sau minloc=n-max+2 (in caz contrar).

Pentru a genera o schema de transport a cainilor vom considera configuratiile valide ca fiind varfurile unui graf.

Exista arc de la configuratia i la configuratia j in acest graf daca din configuratia j se poate ajunge in configuratia i

cu o barca cu minloc locuri.

Vom parcurge BFS acest graf plecand din configuratia finala (configuratia 0, in care nu exista nici un caine pe malul 0, malul de plecare), pana cand ajungem in configuratia initiala (configuratia 1, in care nu exista nici un caine pe malul 1).

In timpul parcurgerii BFS retinem pentru fiecare configuratie si nr minim de traversari necesare pentru configuratia respectiva.

Pentru evaluare au fost utilizate 10 teste (numerotate de la 0 la 9) si s-au acordat 10 puncte pe test.

Inapoi

© 2002 - 2004 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com