Jump to content
K1d0r3L

Intrebare test Bitdefender !!!

Recommended Posts

Salut ,

Sunt curios daca stie cineva raspunsul la urmatoarea intrebare :

Sunt 25 de innotatori si 5 piste de inot cum determini care sunt primii 3 inotatori cei mai rapizi?

Nu exista cronometru !!!!

Eu personal nu stiu raspunsul si nici tovarasu' care a dat testul.

Aveti vreo idee?

Este o problema similara cu determinarea maximului unui numar, in acest caz a trei. Impart inotatorii in 5 multimi de cate cinici, determini pe cel mai rapid din fiecare submultime. Vei obtine 5 inotatori (cate un castigator pe submultime) dupa care determini maximul pentru submultimea formata din cei 5. Se presupune ca fiecare inoata o singura data si fiecare are aceiasi capacitate (adica inoata la fel de repede oricand). Ai nevoie in total de 25 / 5 + 1 = 6 curse.

Link to comment
Share on other sites

@Ganav nu e adevarat. 5 dintr-o serie pot fi mai rapizi decat cel mai rapid din alta serie. Trebuie generate toate submultimele de 5 astfel incat fiecare inotator sa se raporteze la toti ceilalti inotatori.

Dupa sortezi avand ca reper toate submultimile.

Sunt pe tel si e destul de aiurea cu butoanele astea mici.

Link to comment
Share on other sites

Cum as fi rezolvat eu problema :

1. Generam toate submultimele de 5 inotatori din cei 25. (Backtracking )

2. Avem un vector de frecventa inotatori[25] = {0,0, ... , 0} , unde indicii vectorului reprezinta fiecare inotator.

3. Pentru fiecare submultime adun pozitia pe care a terminat in vectorul de frecventa si o sa avem astfel:

Cel care va fi primul, inseamna ca va castiga toate cursele din toate submultimele si o sa aiba cel mai mic numar in vectorul de frecventa (Se aduna 1 de fiecare data cand castiga).

Cel care va fi al doilea, inseamna ca va castiga toate cursele din toate submultimele cu exceptia curselor in care va fi alaturi de cel de pe primul loc (Se aduna 1 de fiecare data cand castiga, 2 se aduna atunci cand va iesi pe locul 2)

Cel care va fi al treilea, inseamna ca va castiga toate cursele din toate submultimele cu exceptia cursei in care va fi alaturi de cel de pe primul loc, cel de pe al doilea loc, si ambii. (Se aduna 1 de fiecare data cand castiga, 2 se aduna de doua ori, atunci cand va fi in cursa cu primul si atunci cand va fi in cursa cu al doilea, iar 3 se aduna o singura data atunci cand 1 si 2 sunt in aceeasi cursa cu el).

Dupa ne uitam in vectorul de frecventa si luam indicele pentru minim (1 loc) si tot asa pana obtinem toate locurile.

Edited by tjt
Link to comment
Share on other sites

Cum as fi rezolvat eu problema :

1. Generam toate submultimele de 5 inotatori din cei 25. (Backtracking )

2. Avem un vector de frecventa inotatori[25] = {0,0, ... , 0} , unde indicii vectorului reprezinta fiecare inotator.

3. Pentru fiecare submultime adun pozitia pe care a terminat in vectorul de frecventa si o sa avem astfel:

Cel care va fi primul, inseamna ca va castiga toate cursele din toate submultimele si o sa aiba cel mai mic numar in vectorul de frecventa (Se aduna 1 de fiecare data cand castiga).

Cel care va fi al doilea, inseamna ca va castiga toate cursele din toate submultimele cu exceptia curselor in care va fi alaturi de cel de pe primul loc (Se aduna 1 de fiecare data cand castiga, 2 se aduna atunci cand va iesi pe locul 2)

Cel care va fi al treilea, inseamna ca va castiga toate cursele din toate submultimele cu exceptia cursei in care va fi alaturi de cel de pe primul loc, cel de pe al doilea loc, si ambii. (Se aduna 1 de fiecare data cand castiga, 2 se aduna de doua ori, atunci cand va fi in cursa cu primul si atunci cand va fi in cursa cu al doilea, iar 3 se aduna o singura data atunci cand 1 si 2 sunt in aceeasi cursa cu el).

Dupa ne uitam in vectorul de frecventa si luam indicele pentru minim (1 loc) si tot asa pana obtinem toate locurile.

Nu ai nevoie de toate combinatiile deoarece esti interesat de un maxim. Practic, problema poate fi asociata cu sortarea unei multimi de numere folosind metoda divide et impera. Fiecare inotator are aceiasi viteza maxima cu inoata de fiecare data, indiferent din ce multime face parte (cu cine concureaza).

Link to comment
Share on other sites

Nu ai nevoie de toate combinatiile deoarece esti interesat de un maxim. Practic, problema poate fi asociata cu sortarea unei multimi de numere folosind metoda divide et impera. Fiecare inotator are aceiasi viteza maxima cu inoata de fiecare data, indiferent din ce multime face parte (cu cine concureaza).

Dar nu ai cum sa afl viteza lui maxima, daca stiai asta problema era foarte simpla.

Edit: Da, ai dreptate. Se reduce tot la aflarea unui maxim.

Pui 5 sa inoate simultan. Cel de pe locul 1 ramane in bazin. ( 25 - 5 = 20 persoane ramase)

Mai adaugi 4 persoane. Cel de pe locul 1 ramane in bazin. (20 - 4 = 16 persoane ramase)

Mai adaugi 4 persoane. Cel de pe locul 1 ramane in bazin. (16 - 4 = 12 persoane ramase)

Mai adaugi 4 persoane. Cel de pe locul 1 ramane in bazin. (12 - 4 = 8 persoane ramase)

Mai adaugi 4 persoane. Cel de pe locul 1 ramane in bazin. (8 - 4 = 4 persoane ramase)

Mai adaugi 4 persoane. Cel de pe locul 1 ramane in bazin. (4 - 4 = 0 persoane ramase(

Am aflat locul 1 si il eliminam din cele 25 de persoane. Raman 24 de persoane si repetam procedura.

E nevoie de 18 tururi in total pentru a afla primii 3

Edited by tjt
Link to comment
Share on other sites

Parerea mea:

Pui 5 inotatori.

Din cei 5 ii pastrezi doar pe primii 3 (ultimii 2 ii elimini si ii inlocuiesti cu alti 2).

Repeti chestia asta cu toti inotatorii.

(ai 11 curse) (25-5 = 20 de inotatori ramasi luati cate 2 => 10 curse + 1 initiala)

La final raman doar top 3 (selectie naturala).

Link to comment
Share on other sites

parerea mea:

problema are rezolvare doar in cazul in care inotatorii isi pastreaza viteza de inot in toate cursele (viteza constanta), caz in care byte-ul a aratat rezolvarea

insa lucrul asta nu este omenesc (sau calaresc, apropos de varianta cu cai), deci in practica problema nu are rezolvare, deoarece intrecerea se transforma in campionat. iar intr-un campionat locul 1 nu este mai rapid ca locul 15, ci doar a acumulat mai multe puncte per ansamblu

Link to comment
Share on other sites

Salut ,

Sunt curios daca stie cineva raspunsul la urmatoarea intrebare :

Sunt 25 de innotatori si 5 piste de inot cum determini care sunt primii 3 inotatori cei mai rapizi?

Nu exista cronometru !!!!

Eu personal nu stiu raspunsul si nici tovarasu' care a dat testul.

Aveti vreo idee?

Scuze, solutia de mai devreme nu este valida deoarece nu trateaza cazul in care intr-un grup de inotatori se gasesc inotatori mai inceti ca si cel mai rapid din grup, dar care este si cel mai rapid dintre toti din toate grupele. Ceilalti inotatori mai lenti pot fi totusi mai rapizi ca si cei mai rapizi din celelalte. Prin grup ma refer la un grup de cinci inotatori care concureaza simultan.

O metoda simpla ar fi selectarea primilor trei din fiecare grupa si compararea acestora. Selectarea doar a unui singur nu este suficienta din cauza problemei de mai sus.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...