|
|
|
Thursday, 24 march 2011 |
|
|
|
Vinul otravit |
Proposed by
Skyler |
|
| (52 comments) | 20.873 times displayed |
 |
Esti conducatorul unui imperiu medieval si vrei sa dai o petrecere maine. Ai achizitionat 1000 de sticle de vin pe care planuiesti sa le deschizi maine, insa aflii ca una dintre ele a fost otravita. Otrava nu da nici un simptom pana in momentul mortii, ce survine dupa 18-20 de ore. Din fericire ai o mana de sclavi ce pot fi sacrificati pentru a descoperi sticla otravita, insa nu foarte multi.
Care e numarul minim de sclavi ce pot fi folositi pentru a testa vinul, avand la dispozitie doar 24 de ore? |
|
|
Numerotati sticlele folosind sistemul binar(baza 2) pentru a afla numarul minim de sclavi.
De exemplu, pentru 8 sticle de vin avem nevoie de minim 3 sclavi: 8 = 2^3.
_______ |Sticla 1 |Sticla 2 |Sticla 3|Sticla 4 |Sticla 5|Sticla 6 |Sticla 7 |Sticla 8|
Sclavul a |__0___|__1___|__0___|__1___|__0___|__1___|__0___|__1___|
Sclavul b |__0___|__0___|__1___|__1___|__0___|__0___|__1___|__1___|
Sclavul c |__0___|__0___|__0___|__0___|__1___|__1___|__1___|__1___|
In acest fel, fiecare sclav o sa bea din sticla in dreptul careia apare 1. Daca mor toti 3, sticla otravita e 8. Daca mor primii 2, sticla otravita e 4.
Pentru a testa 1000 sticle e nevoie de minim 10 sclavi, cu care putem forma 1024 combinatii (2^10) |
|
|
|
|
|
 |
Search problems by keywords
|
|
|
|
|
|
|
|
|
|
|
|
Today's Problem
Top 10 most viewed problems