#42 Aruncari cu bile – problema de interviu

by dumitru on 17 februarie 2014 · 44 comments

Esti intr-o cladire de 100 de etaje si ai la dispozitie doua bile identice. Se stie despre bile ca daca le arunci de la o inaltime mai mica de X etaje nu se sparg, iar de la inaltime mai mare se sparg. Se cere sa se gaseasca cel mai mare etaj  de la care se poate arunca o bila fara sa se sparga. De cate aruncari este nevoie ?

Propusa de Bogdan S.

(intalnita si in cartea “Cracking the coding interview”, usor modificata)

Probleme similare:

[Arata raspunsurile] [Raspunde si tu!]

{ 44 comments… read them below or add one }

1 Sandu 18 februarie 2014 la 4:15

Fie x estajul pe care il cautam.. atunci numarul de aruncari ar fi:
(x div 3)+3 daca x<100 sau
33 daca e 100.

Răspunde

2 Sandu 18 februarie 2014 la 4:16

Fie x estajul pe care il cautam.. atunci numarul de aruncari ar fi:
(x div 3)+2 daca x<100 sau
33 daca e 100.

Răspunde

3 Paul 18 februarie 2014 la 21:14

Se arunca de la etajele 10,20,30…100 pana se sparge prima bila.
Presupunem ca s-a spart la 70.
Apoi se arunca bila 2 de la 61,62,63…69 pana se sparge sau nu.
In cel mai defavorabil caz se fac 100/10+9 =19 pasi

Răspunde

4 vadim 18 februarie 2014 la 21:49

19 maximum

Răspunde

5 Lelu_Vs 19 februarie 2014 la 19:33

Etajul X-1. Nr de incercari : X:2. Parerea mea…

Răspunde

6 ady 20 februarie 2014 la 16:38

maxim 14 pasi , incepem sa aruncam intii 14 etaje , daca se strica arumcam de la 1 pina la 13 si vedem exact unde s-a stricat , daca nu se strica , aruncam la 14+13, ca sa nu creasca numarul de pasi in caz ca se sparge, dupa care aruncam la 14+13+12 si asa mai departe

Răspunde

7 jony 20 februarie 2014 la 17:54

2. atat cate bile sunt.

Răspunde

8 Lelu_Vs 21 februarie 2014 la 22:39

In problema nu se specifica ce se intampla la etajul X. Se sparg sau nu bilele ? Asta ar completa enuntul.

Răspunde

9 Dan D 27 februarie 2014 la 17:43

cel mai mare etaj de la care se poate arunca o bila fara sa se sparga
este X-1

Este nevoie de X+1 incercari, pornind de la etajul 1 …. pana la X+1,pentru a se determina primul etaj la care se va sparge bila 100%.
Aruncarea de la etajul X nu certifica ca o bila s-ar sparge(probabil de aceea avem 2 bile).

Numarul maxim de aruncari presupun ca este X+2.

Răspunde

10 Marius 28 februarie 2014 la 16:41

Aruncam prima bila de la etajele pare ( 2,4,6,8….) . In momentul in care se sparge prima bila (etajul x), stim ca etajul cel mai mare de la care poate fi aruncata o bila este fie x-1 fie x-2. Aruncam a doua bila de la etajul x-1. Daca nu se sparge raspunsul este x-1, daca se sparge raspunsul este x-2.
Ex: prima bila se sparge la etajul 54. O aruncam pe a doua de la etajul 53. Daca nu se sparge 53 este cel mai mare etaj, daca se sparge 52 este cel mai mare etaj pentru ca am aruncat deja de la 52 prima bila.(48,50,52,54)

Răspunde

11 eu 3 martie 2014 la 12:59
12 Catalin Manea 7 martie 2014 la 14:10

Urci cite un etaj si arunci una din bile pina la etajul la care se sparge. Rezulta ca etajul limita este cel cu numarul mai mic cu 1 decit cel la care se sparge bila. Cita vreme bila nu se sparge, te poti folosi in continuare de ea pina se sparge si ai in permanenta a doua bila intacta.

Răspunde

13 Alex 7 martie 2014 la 15:07

Am stat si m-am tot gandit mai putin de maxim 18 aruncari nu am gasit o solutie:
Iei prima bila si o arunci de la etajul 10, apoi 20, 30, 40, 50, 60, 70, 80 , 90.
Daca cumva crapa iei a doua bila si incepi de la etajul ultimei aruncari (daca a crapat cand ai aruncat-o de la 80, cu a doua bila incepi de la et 71) si arunci din ce in ce mai sus pana cand crapa si a doua bila.
Daca cu a crapat pana la 90, incepi si o arunci din etaj in etaj pana cand gasesti etajul de la care crapa.

Orice s-ar intampla gasesti etajul in maxim 18 aruncari (in cel mai rau caz era etajul 99)
Nu am luat in calcul etajul 100 pentru ca mai sus de etajul respectiv nu poti ajunge ca sa arunci bila, deci l-am scos din start

Răspunde

14 Ionut 9 martie 2014 la 20:36

50 aruncari

Răspunde

15 Gabriel 14 martie 2014 la 1:50

Si de la ultimul etaj, atata timp cat NU le arunc pe langa cladire ci pe podeaua ultimului etaj. Nu pare sa fie specificat UNDE sa arunci bilele, asa ca se poate dintr-o singura aruncare.

Răspunde

16 Gabriela Vasile 16 martie 2014 la 14:07

Am voie să leg bila de o parașută?

Răspunde

17 Daniel 18 martie 2014 la 8:53

Etajul este x si este nevoie de x/2+1 incercari.

Răspunde

18 alam 19 martie 2014 la 18:32
19 kinder 20 martie 2014 la 9:35

etajul este clar 100(nu se specifica faptul ca bila trebuie sa atinga solul). numarul de incercari cred ca e divindeEtImpera(inaltimeaEtajului100);

Răspunde

20 Lelu_Vs 25 martie 2014 la 22:18

Eu astept si raspunsul “Oficial”

Răspunde

21 Nicolas 27 martie 2014 la 21:51

Incepand de la primele etaje vor fi (100/4)+1 = 26 de aruncari, maxim.
De ce 4? Pentru ca prima data se arunca de la et. 4.
Daca s-ar sparge bila este logic sa arunci de la et 2 iar prin eliminare (se spage sau nu) afli etajul limita.

Răspunde

22 alex 30 martie 2014 la 22:29

7 bile. Mereu arunci de la jumatatea intervalului. La 100 arunci de la 50, daca s-a spart arunci de la 25 si intervalul tau este (0, 50), daca nu s-a spart arunci de la 75 si intervalul este ( 50,100) . Continui asta pana ramai cu intervalul de lungime 1.

Răspunde

23 Nicolas 7 aprilie 2014 la 0:33

Cu totii uitati ca aveti doar 2 bile ? Odata sparte nu mai ai cu ce arunca !

Răspunde

24 Dragoș 7 aprilie 2014 la 16:57

Dacă bila se sparge la etajul 1 – încercarea a luat sfârșit !! ai nevoie doar de una!( !!!!!!!E OBLIGATORIU să începi de la ETAJUL 1 !!!!!!!)
Dacă nu, continui etaj cu etaj…până la 100 …deci va fi un nr. de încercări să spunem y ={1, 100} …dacă nu am uitat cumva semnul pentru intervale. :)

Răspunde

25 Petrica Radu 10 aprilie 2014 la 19:48

Raspuns corect : 18
Impartim cele 100 de etaje in n intervale ( n= 2,4,5,10,20,50)
Luam exact cazul final , celelalte sunt identice ca logica .
n=10
1. Numarum maxim de incercari pentru bila 1 este 9 ( n-1) , adica se va sparge la etajul 90.
2. Numarul maxim de incercari pentru bila 2 este 9 ( 100/n-1)
Deci , numarul maxim de incercari pentru cele 2 bile este n-1+ 100/n-1=9+9=18 .
Se face calculul pentru celelalte valori ale lui n si se vor obtine valori mai mari .
ex. n=5 4+19=23 .

Răspunde

26 Radu Alin 21 mai 2014 la 21:41

Daca ai doar doua bile banuiesc ca raspunsul la intrebarea de cate ori poti sa arunci e evident 2 ori. Prima aruncare nu poti sa o faci de la un etaj mai mare de 2 pentru ca mai ai doar o bila, iar in cazul in care de la etajul 2 aceasta se sparge ai varianta sa o arunci de la etajul 1 si sa nu se sparga. Daca arunci de la 3 si se sparge si ai vrea sa arunci a doua bila de la 2 risti sa o spargi si pe aceasta.
Raspunsul meu este de la etajul 1 sigur nu o sa se sparga si nu mai ai nevoie de a doua bila.

Răspunde

27 Radu Alin 21 mai 2014 la 21:55

In cazul in care ai avea la indemana cate bile vrei se pune problema astfel: prima bila tot timpul o arunci de la etajul 50 si ai doua optiuni:
I bila se sparge si atunci incerci la etajul 25 (a doua bila)
II prima bila nu se sparge si urci la etajul 75 si problema continua tot asa: in cazul in care bila se sparge mergi la jumatate de la 25 ori la 13 ori la 38 iar in cazul in care dupa 50 nu se sparge si la 75 incerci ori 63 ori 88 si tot asa.
Daca esti un pic de informatician (desi nu ma prea pricep) problema se scrie astfel:
fie I si j apartine interv [1; 100] si I si j apartine lui N (nr naturale nenule)
fie j un nr random (necunoscut)
atunci for I= 50
daca I=j atunci j=50 daca nu
daca I>j atunci I :=I+I/2Daca nu
atunci I:=I-I/2 si tot asa pana I=J

Răspunde

28 Alex 8 iunie 2014 la 22:18

..si iarasi logic: o singura aruncare! …multi se intreaba: ”cum asa?” ..poi, si in text scrie: ”se stie ca daca se arunca de la X…” mai mare sau mai mica nu conteaza! Odata ce stii de la ce etaj se sparge mai ai nevoie doar sa o arunci! :)

Răspunde

29 Ionut 2 iulie 2014 la 14:45

Cel mai mare etaj de la care se poate arunca o bila fara sa se sparga este x-1 si nu este nevoie de nicio incercare deoarece stim ca bilele nu se vor sparge (din enunt)

Răspunde

30 Catalin 8 iulie 2014 la 23:48

Radu Alin are dreptate. Acelasi lucru ma apucasem sa scriu, apoi am vazut si raspunsul lui. Este nevoie de maxim 7 aruncari. Imparti pe 100 la 2, pana ajungi la 1. De cate ori il imparti, reprezinta nr de aruncari necesare, iar 1, este nr etajului cand aplici formula.

Răspunde

31 mircea 23 august 2014 la 15:56

6 incercari. arunci de la etajul 50 daca se sparge sau nu iti raman 49 de etaje dupa arunci de la etajul 25 daca se sparge sau nu raman 24 de etaje acuma arunci de la etajul 12 daca nu se sparge aici atunci iti raman 11 etaje acuma arunci de la etajul 6 orice ar fi raman 5 etaje arunci acuma de la etajul 3 si vezi care e 2 raman si mai arunci odata.in cazut in care la 12 se spargea atunci ramaneau 13 auncai de la 7 raman 6 etaje arunci de la 3 raman inca 1 aruncare

Răspunde

32 Lelu_Vs 30 ianuarie 2015 la 12:49

Presupunem ca la experimentul facut de tine se sparge prima bila la et. 50. Arunci de la etajul 25. Se sparge si bila ramasa. In situatia asta care este etajul de la care incep sa se sparga bilele ??? 4 ? .. 8? …. Sau 23? …. Conform carui calcul ? Teoria ta se aplica pt aflarea numarului de bile (care se sparg) necesare identificarii etajului X.

Răspunde

33 magicul 25 septembrie 2014 la 14:36

Dacă de la etajul x se sparge bila, înseamnă că e clar:
mai cobori un etaj și poți arunca bila fără ca să se spargă.
Răspuns: o singură încercare.

Răspunde

34 Sorin 8 decembrie 2014 la 18:59

Intrebarea nu cred ca e formulata cum trebuie. Presupun ca autorul incearca sa vada care e numarul minim de incercari absolut necesare (deci pentru cea mai defavorabila pozitie). Din 10 in 10 merge, dar are o hiba: cu cit te duci spre un etaj mai inalt, cu atit numarul de incercari creste (se tot aduna etaje, dar intre ele numarul cel mai defavorabil de incercari nu scade. Ca sa evitam asta, trebuie sa alegem un prim etaj si o procedura in asa fel incit numarul maxim de incercari sa ramina constant. Pentru fiecare noua incercare cu prima bila, se aduna o unitate, deci trebuie scazuta o unitate din incercarile cu cea de a doua bila cind se sparge prima. Daca incepem cu n etaje, a doua oara incercam cu n-1, samd. pina la 100, cind trebuie sa mai avem doar 1. Deci 1+2+3+… +n=100, deci [n(n+1)]/2=100.. rezolvind ecuatia se obtin 13. 65 etaje (dar nu se poate), deci se rotunjeste la 14. prima oara trebuie incercat cu etajul 14. Daca se sparge prima bila, vor fi cel mult 13 incercari cu a doua (in total 14). Daca nu se sparge, se continua cu etajul 14+13=27 Daca se sparge, deja sunt doua incercari, dar mai sunt necesare cel mult 12 ca sa se determine etajul, care inseamna iar cel mult 14. Daca nu se sparge, se continua cu etajul 14+13+12=39 samd.

Problema se poate generaliza pentru m etaje: numarul minim de incercari necesare pentru cea mai defavorabila pozitie este partea intreaga plus 1 a solutiei pozitive a ecuatiei: n^2 + n -2m = 0

Răspunde

35 Eistein 6 ianuarie 2015 la 23:44

Aruncam de la 50 si 51(2 aruncari),daca se sparge la 50 si 51 ,aruncam de la 25 si 26 (2 aruncari),daca se sparg la ambele aruncam de la 12 si 13 (2 aruncari),daca se sparg,6 si 7 (2 aruncari),daca se sparg 3 (o aruncare) avem etaju 2, deci 9 aruncari 10 maxim

Răspunde

36 Lelu_Vs 30 ianuarie 2015 la 12:42

Einstein … daca se sparg la 50 si 51, dupa aia nu mai ai cu ce arunca. In enunt nu se specifica un numar infinit de bile.

Răspunde

37 Bush 11 februarie 2015 la 16:10

7 aruncari in caz ca nu nimeresti din primele 6 (prima de la 100/2=50; a doua de la 25 sau 75 a treia de la 13, 38, 63 sau 88 si asa mai departe)

Răspunde

38 Bush 11 februarie 2015 la 16:21

In caz ca exprimarea a fost ambigua: aruncam bila de la etajul 50 astfel eliminam din start 50 de etaje apoi de la jumatatea distantei pana la baza sau varful cladirii(25 sau 75in functie de caz) eliminand inca 25 de etaje, apoi din nou la jumatatea distantei si tot asa… In cel mai rau caz se efectueaza 6 aruncari
(Ex: et 50 bila se sparge,
et 25 bila nu se sparge,
et 38 bila nu se sparge,
et 44 bila se sparge,
et 41 bila nu se sparge,
et 43 bila se sparge asa ca este logic ca raspunsul este 42)

Răspunde

39 marius chivu 11 februarie 2015 la 21:32

RASPUNS 7 ARUNCARI

Răspunde

40 Oturan 4 martie 2015 la 21:45

o iei de la etajul 1 si arunci cu o b ila paana se sparge
ex etaju 1 nu se sparge
etaju 2 nu se sparge
etaju 3 se sparge
rezulta etaju max este etajul 2

Răspunde

41 Gigi Laurian 3 aprilie 2015 la 15:50

14 aruncari.

Prima aruncare a primei bile o fac de la etajul 14. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 13, am nevoie de 1+13=14 aruncari.

Daca prima bila nu s-a spart la etajul 14, o arunc de la etajul 14+13=27. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 26, am nevoie de 2+12=14 aruncari.

Daca prima bila nu s-a spart la etajul 27, o arunc de la etajul 27+12=39. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 38, am nevoie de 3+11=14 aruncari.

Si asa mai departe, pana la etajul 14+13+12+11+10+9+8+7+6+5+4=99.

Ca generalizare, pentru o cladire cu N etaje, nr de aruncari de care ai nevoie este dat de cel mai mic numar natural care satisface inecuatia:
x(x+1)/2>=N.

Răspunde

42 eugenia 23 aprilie 2015 la 1:13

haha de 2 aruncari e nevoe daca avem doar 2 bile?)))))

Răspunde

43 Liviu 11 ianuarie 2017 la 23:06

Maximum 18 aruncari

Răspunde

44 Liviu 11 ianuarie 2017 la 23:15

Pasul optim dupa care se fac incercarile (din cat in cat) este radical indice 2 din numarul de etaje. radical indice 2 din 100 este 10.

Răspunde

Leave a Comment

*

Previous post:

Next post:

</