| Blogs > Shady Sands |
|
Shady Sands
United States4021 Posts
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break? 1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc. Once you have calculated this for the 100-floor building, what is the answer for an n-floor building?   | ||
|
AnachronisticAnarchy
United States2957 Posts
| ||
|
TOCHMY
Sweden1692 Posts
least number of drop attempts: 2, cuz you only have, at most, 2 rocks? Dont mind the spoiler, I misunderstood the question... | ||
|
Warmonger
United States69 Posts
On November 21 2012 06:46 AnachronisticAnarchy wrote: Is this a trick question? It seems impossible to do it with only 2 rocks. Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks | ||
|
AiurZ
United States429 Posts
for an n-floor building u just find the minimum of (n/x)+x=y and that is the amount of floors u skip each try (for a 100 floor building it is 10). | ||
micronesia
United States24665 Posts
Except they used eggs. | ||
|
L3gendary
Canada1470 Posts
nvm i skipped over the u can only break it twice part, the egg one made it more clear to me. The steps of 10 seems right. For N case it'd be 2*root(N)-1. | ||
|
Shield
Bulgaria4824 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks It sounds like it works, but is it the fastest way? | ||
|
AnachronisticAnarchy
United States2957 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks You only have 2 rocks, though. I guess if you want to discard that limit, you could do this: 1. drop a rock from the 50th floor 2a. if it breaks, go to floor 25 2b. if it doesn't break, go to floor 75 3a,a: if it breaks, go to floor 13 3a,b: if it doesn't break, go to floor 37 3b, a: if it does break, go to floor 63 3b, b: if it doesn't break, go to floor 87 and so on and so on By doing this, you maximize the amount of floors each drop covers, until you find the floor you're looking for. I'm not fond of the question though. Even without the 2-rock limit, there's the fact that the appropriate floor is random, so odds are you would stumble upon the answer before you finish the process you are doing and rule out everything but the answer. | ||
|
stenole
Norway868 Posts
| ||
|
Melliflue
United Kingdom1389 Posts
On November 21 2012 06:53 Warmonger wrote: Not impossible, it would just take a while without further assumptions/knowledge. + Show Spoiler + 1.)Drop the first rock from halfway up the building, N/2 2a.)If it breaks start on the 1st floor and keep going up a floor until it breaks 2b.)If it doesn't break start on the 51st floor (N/2 +1) and keep going up a floor until it breaks You can do better than this. + Show Spoiler + If the rock doesn't break (case 2b) then you can drop a rock from the 75th floor using the same argument. If it breaks then start on 51st floor, if it doesn't then try higher. I doubt that is optimal though. Edit: On November 21 2012 07:12 AnachronisticAnarchy wrote: You only have 2 rocks, though. I guess if you want to discard that limit, you could do this: 1. drop a rock from the 50th floor 2a. if it breaks, go to floor 25 2b. if it doesn't break, go to floor 75 3a,a: if it breaks, go to floor 13 3a,b: if it doesn't break, go to floor 37 3b, a: if it does break, go to floor 63 3b, b: if it doesn't break, go to floor 87 and so on and so on By doing this, you maximize the amount of floors each drop covers, until you find the floor you're looking for. I'm not fond of the question though. Even without the 2-rock limit, there's the fact that the appropriate floor is random, so odds are you would stumble upon the answer before you finish the process you are doing and rule out everything but the answer. That's a standard binary search or bisection search. I can't remember the technical term for it. It is the most efficient way with enough rocks. I am not sure I follow your argument for why you don't like the question. The floor is random, but the question is what is the least number of drops needed to be certain that you know which floor it is. | ||
|
spinesheath
Germany8679 Posts
Heh, guess I was wrong about the 10 20 30 solution being right. | ||
|
Cyber_Cheese
Australia3615 Posts
I think the working the way up in multiples of 10 thing was best for 2 stones only, sqrt(floors) I'm not about to sit down and calculate every scenario though.. | ||
|
Phael
United States281 Posts
+ Show Spoiler + A straightforward solution would be to drop the first rock every 10 floors until it breaks, then drop the second rock from the last floor that didn't break up in increments of 1. Ex: drop at 10, 20, 30, 40, 50 .. break. Ok, second rock: 41, 42, 43, 44 ... break. Highest floor: 43. This would give us a solution of 19, which isn't optimal, because you're "wasting" potential drops if the rock cracks on floor 9, for example, vs floor 99. So instead, drop the first rock at floor 14, then floor 27 (14+13), then floor 39 (14+13+12), etc. This way, the "worst case scenario" of a rock breaking at 14 means you drop 13 more times, the WCS of a rock breaking at 27 would be dropping 12 more times, etc. so in total, you should only need 14 drops no matter which floor the rocks crack on. How did I get 14? I recognized that you need 1 + 2 + 3 + 4 + 5 + ... + d >= number of floors, and for 100, d = 14. General solution + Show Spoiler + General solution for d drops on a building with n floors: Following from previous, 1 + 2 + 3 + 4 + 5 + ... + d >= n. d*(d+1)/2 >=n d^2 + d - 2n >= 0 By the quadratic equation, the positive solutions: d >= (root(8n+1)-1)/2 so minimum number of drops needed = ceiling((root(8n+1)-1)/2) | ||
|
Warmonger
United States69 Posts
On November 21 2012 07:12 darkness wrote: It sounds like it works, but is it the fastest way? You are right, I overlooked being able to re-use the first rock if it didn't break. In which case the "best" method may be defined differently for different needs. Are we looking for fastest average solution for a building with N stories? The solution with least attempts on worst-case? I don't have the knowledge to do either off the top of my head, but I'm sure some CS major can do it fairly easily. | ||
|
CoughingHydra
177 Posts
On November 21 2012 07:06 L3gendary wrote: logN/log2 ? rounded of course. This is the first thing that came to my mind too ( binary search algorithm ). http://en.wikipedia.org/wiki/Binary_search_algorithm EDIT: Nevermind  | ||
|
Blazinghand
United States25551 Posts
| ||
|
opisska
Poland8852 Posts
| ||
|
AnachronisticAnarchy
United States2957 Posts
| ||
|
Varanice
United States1517 Posts
On November 21 2012 07:22 Phael wrote: Solution for 100 floors: + Show Spoiler + A straightforward solution would be to drop the first rock every 10 floors until it breaks, then drop the second rock from the last floor that didn't break up in increments of 1. Ex: drop at 10, 20, 30, 40, 50 .. break. Ok, second rock: 41, 42, 43, 44 ... break. Highest floor: 43. This would give us a solution of 19, which isn't optimal, because you're "wasting" potential drops if the rock cracks on floor 9, for example, vs floor 99. So instead, drop the first rock at floor 14, then floor 27 (14+13), then floor 39 (14+13+12), etc. This way, the "worst case scenario" of a rock breaking at 14 means you drop 13 more times, the WCS of a rock breaking at 27 would be dropping 12 more times, etc. so in total, you should only need 14 drops no matter which floor the rocks crack on. How did I get 14? I recognized that you need 1 + 2 + 3 + 4 + 5 + ... + d >= number of floors, and for 100, d = 14. General solution + Show Spoiler + General solution for d drops on a building with n floors: Following from previous, 1 + 2 + 3 + 4 + 5 + ... + d >= n. d*(d+1)/2 >=n d^2 + d - 2n >= 0 By the quadratic equation, the positive solutions: d >= (root(8n+1)-1)/2 so minimum number of drops needed = ceiling((root(8n+1)-1)/2) I was getting close to this for the 100 floor version, but you sir are a genius. | ||
| ||
|
|
WardiTV European League
ByuN vs NightPhoenix
HeRoMaRinE vs HiGhDrA
Krystianer vs sebesdes
MaxPax vs Babymarine
SKillous vs Mixu
ShoWTimE vs MaNa
Replay Cast
RSL Revival
herO vs SHIN
Reynor vs Cure
OSC
WardiTV European League
Scarlett vs Percival
Jumy vs ArT
YoungYakov vs Shameless
uThermal vs Fjant
Nicoract vs goblin
Harstem vs Gerald
FEL
Korean StarCraft League
CranKy Ducklings
RSL Revival
FEL
[ Show More ] |
|
|
EPT
