CareerCup

It can be done in 13 drops...

http://www.cs.umd.edu/~gordon/ysp/egg.pdf

It can be done in 14, and that can be proved to be optimal.

If I remember correctly, the sequence of floor choices is:

14,14+13,14+13+12,14+13+12+11,...

I solved it some while ago.
The solution is, as you can see, DP.

For B=2, there's a nice formula (you can see it in the assert - the condition that I put there):
F max = (D * (D+1))/2

I paste the code again, preserving spaces:

long[][] fMaxTable = new long[MAX_D + 1][MAX_B + 1];
		
		for (int i = 1; i <= MAX_B; i++)
			fMaxTable[1][i] = 1;
		
		for (int i = 1; i <= MAX_D; i++)
			fMaxTable[i][1] = i;
		
		for (int d = 2; d <= MAX_D; d++)
			for (int b = 2; b <= MAX_B; b++)
			{
				long t = 1 + fMaxTable[d - 1][b] + fMaxTable[d - 1][b - 1];
				
				if (fMaxTable[d - 1][b] == -1 || fMaxTable[d - 1][b - 1] == -1
					|| t > (2L << 32))
					t = -1;
				
				if (b == 2)
					if (t !=  (long)d * ((long)d + 1L) / 2L)
						throw new Error("" + d + " " + b + " " + t + " " + (long)d * ((long)d + 1L) / 2L);
				
				fMaxTable[d][b] = t;
			}

This problem can be solved in exactly ln(100).
Here is how:
first try from 50th floor -- if it breaks then try 25th floor else try 75th floor
second trying 25th floor -- if breaks then try 12th floor else try 38th floor
...
This was u can get the answer in Log(100) to the base 2.
--KM

@LOLer , what are you talking about... you are going to play with balls...oh no...Jesus!!!
How could you think of dropping balls from 100th floor, if by mistake you loose one, then you will remain one baller and if you loose the other one....your done...ball-less...can't just imagine..too much...help these idiots talking all these nonsenes....
Jokes apart, the problem is exactly the same as Egg Dropping problem, find the generalized solution to egg dropping problem for more that 2 eggs, here

http://www.scribd.com/doc/7217370/Egg-Puzzle-Generalized-Solution-for-Any-Number-of-Eggs

14 is possible, but since they only ask max 20 here's an easier way to do it;

i) Drop the first bulb 10 by 10 floors at a time 10, 20, 30... until it breaks
ii) As soon as it breaks go back 9 floors and start going up one by one. So if it breaks in floor 60, you go to 51, 52, 53... until the second breaks

A maximum of 19 is needed in this method

Assume the max num of floor is F,

A=int(sqrt(F))
B=int(F/A)

then max time T=A+B-1


example, F=100,
A=10, B=10, T=20-1=19

This is classic problem in dynamic programming. Use the formula
q(q+1)/2 >=100

q = 14.

Drop the first bulb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Binary search will result in 50. Other techniques mentioned above give under 20 which is better than binary search.

Problem can be solved with derivative methods.

Y = 100/n + n + constant

dY/dn = -200/(n^2) + 1 = 0

And you get n = 14

I am not sure if i understood correctly..
1. let say we are droping from floor n which is max drop number as well
2. My next floor for drop would be n+n-1 (we have dropped as n so remaing max number of drops are n-1
3. my next floor would be n-2 and so on

So we we sums up all of them then
n+(n-1) + (n-2)+ (n-3)+ ....+1 <=100 (assuming would be final floor)

n(n+1)/2 <=100
or in other words n<=14
Hence worst case n=14

correct me if i am wrong
Ravi

This is a particularization of the Egg Drop problem (Google CodeJam 2008, Practice Problems) for F = 100 and B = 2

Using the optimal algorithm, the number of drops should not exceed 14.

Here's the code to precalculate the max. allowed F for every D and B:

long[][] fMaxTable = new long[MAX_D + 1][MAX_B + 1];

for (int i = 1; i <= MAX_B; i++)
fMaxTable[1][i] = 1;

for (int i = 1; i <= MAX_D; i++)
fMaxTable[i][1] = i;

for (int d = 2; d <= MAX_D; d++)
for (int b = 2; b <= MAX_B; b++)
{
long t = 1 + fMaxTable[d - 1][b] + fMaxTable[d - 1][b - 1];

if (fMaxTable[d - 1][b] == -1 || fMaxTable[d - 1][b - 1] == -1
|| t > (2L << 32))
t = -1;

if (b == 2)
if (t != (long)d * ((long)d + 1L) / 2L)
throw new Error("" + d + " " + b + " " + t + " " + (long)d * ((long)d + 1L) / 2L);

fMaxTable[d][b] = t;
}