   Is there such an algorithm?
  I came across a programming problem lately and I was kinda baffled by it. I didn''t come up with a single algorithm that could solve it, so that''s why I am asking here, if anyone knows about an algorithm that might do the job.Alright...A small mailbox manufacturer needs to know how many firecrackers his mailboxes can withstand without blowing up. A mailbox has a maximum capacity of crackers (meaning, you cannot fill the mailbox up with more than this amount) and if the mailbox doesn''t explode when filled with the maximum capacity, all is fine.The actual problem though, is the amount of crackers needed. The mailbox manufacturer is quite cheap and wants to save as much as possible on firecrackers, so he asks you to find out how many crackers he has to give you so that you can test the mailbox properly.If you only have one mailbox, then you would have to test it by inserting one cracker, then two, then three... all the way to the mailbox'' maximum capacity. This means, on a mailbox with 100 as its maximum capacity you would need (100 * 101) / 2 crackers.Now, the mailbox manufacturer asks you if you can lower that amount if he gives you several identical mailboxes that you can test on. If you have more than one mailbox, then you could lower that amount by some kind of optimization.The problem is, I don''t know how. My first thought was a divide approach. For each mailbox ''extra'' that you got, you could test less crackers by doing the same thing that you do in a number guessing game, halve the options by choosing half of the input. Meaning if you got two boxes with maximum capacity of 16, you could try 8 at once in the first one and then go up from 9 to 16 on the second one. This is however, not the answer that is needed, nor is it a very optimal one.There are three points to be regarded:1. You must always concider the worst case possible (mailbox explodes at max-capacity)2. If a mailbox doesn''t explode at x crackers, it will not explode at x - 1 ... 1 crackers either.3. Upon explosion a mailbox is either totally destroyed (blown up) or unharmed (meaning it can be used in another test).So, any takes on this one? Anyone? 
  Basicly you do something like a binary search. Put half the max in a mailbox and if it breaks go to 1/4 max; if it withstands then go to 3/4. Just repeat until that pattern until the number is found. ;  You can repeatedly double the number of crackers you try, until you only have 1 mailbox left, at which point you must resort to linear search. ;  That''s assuming your initial guess is under the max capacity. ;  Dobbs - you start at 1, not halfway ;  Nono, see, binary search won''t do. You can''t go halving values since it isn''t optimal enough.The hint I got was to use the Dynamic Programming paradigm, which is a way to construct algorithms from all I''ve known. I am still halfway through the algorithm book I have and don''t want to jump to the dynamic programming part.   -----------------------------Final Frontier Trader   ;  i had a question like this to do for an assignmnt in class, except instead of fire crackers and mailboxes, it was wine and winetesters. there was one bottle of poison wine, among thousands of bottles of good wine, and x amount of testers. you wanted to minimize the amout of wine that was drank, because the wine that is not poisoned is very tasty and you dont wantt the lousy testers drinking it. x testers means 1 or 2 or 3.. to make it easier and easier just like you had 1 or 2 or 3.. mail boxes to save on firecrackers.Anyway, i dont have the algorithm with me, but i did figure it out after a while. All i remember was it kind of sucked, and it involved a concept called dynamic programming, where you basically calculate a bunch of smaller cases in a table and then use those smaller cases to calculate bigger cases.. until you get the final answer.If you think the algorithm is tough, try coding an implementation of it once you figure it out.;  Sounds to me like a relatively straight-foreward problem.... unless i''m missing something.you can increment the amount of fireworks you stuff in by the amount of mail boxes you have. so if you have 5 mailboxes you can increase your ammount of fireworks by 5 everytime... then when one blows up you work backwards. subtracting one until it doesn''t blow up. then you have your number.;  yea its not exactly a hard problem...until the teacher says to find the solution in O(log n) time or something like that. Im a little rusty, but i think your solution is linear, NamelessOne. Even if you increased by 1000 each time, its still linear. You need to decrease the number of possibilities by a factor somehow, ie have root(n) possibilities left to test at each step, not n-5;quote:Original post by sjelkjd  Dobbs - you start at 1, not halfway   Ah I misread the problem anyway, when he said max capacity I thought he meant the amount that blows it up, not the amount it can hold. If I understand it right now, the solution is a generalized version of binary search - instead of dividing the search space in half you divide it into N+1 parts, where N is the number of mailboxes. 