Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: AGM 2015  (Citit de 1304 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« : Mai 30, 2015, 07:47:02 »

Prima editie a concursului AGM va avea loc sambata 30 mai 2015.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #1 : Mai 30, 2015, 18:44:07 »

Cum sa scapă la problema Autobuze3 de condiția de 25 de mutări pentru un șofer? Ideea inițiala a fost ca răspunsul este costul unui MST. Dar cum se construiește răspunsul astfel încât sa nu existe mai mult de 25 de mutări?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #2 : Mai 30, 2015, 19:01:52 »

Muti soferii din autobuzul cu numar mai mic de soferi in autobuzul cu numar mai mare de soferi. Fiecare sofer va fi mutat de cel mult logN ori.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #3 : Mai 30, 2015, 19:17:28 »

Cum se poate demonstra ca este cel mult log(N)? Eu am mutat șoferii din toate autobuzele în autobuzul care avea un șofer cu număr maxim de mutări (asta pentru fiecare nod din arbore) si pica. Adica facem o parcurgere in adancime si pentru fiecare nod, dupa ce rezolvam subarborele sau vedeam cate autobuze ajung in el. Unul dintre acestea trebuie sa treacă mai departe către rădăcina. Si acesta era cel care avea un sofer cu numar maxim de mutari.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #4 : Mai 30, 2015, 19:41:30 »

Pai gandeste-te la cum se muta un sofer s. Fie x numarul de soferi din autobuzul in care e s. Daca se muta soferul s in alt autobuz atunci x va deveni cel putin 2x. Evident, nu se poate intampla asta decat de cel mult logN ori.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #5 : Mai 30, 2015, 19:54:50 »

Sa zicem ca intr-un nod ajung 3 autobuze: unul cu 2 soferi, altul cu 3 și altul cu 5. Atunci nu trebuie sa ii mut pe cei 2 din primul si pe cei 3 din al doilea, in al treilea autobuz? Ultimul va fi cel care va "avansa" catre radacina impreuna cu 10 soferi.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #6 : Mai 30, 2015, 20:55:18 »

Da, e corect.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines