Recursive Mathematical Puzzle from a high school contest The problem appeared on the 2013 SJCNY High School Programming Contest. It was the last question in the set of problems and no team produced a correct answer during the 2.5 hours they had to work on it. Shortest solution that can handle the full range of inputs with a reasonable run time (say under 2 minutes on a Pentium i5) wins.

Vases     

Ryan’s mom gave him a vase with a cherished inscription on it, which he often places on his 
window ledge. He is moving into a high rise apartment complex and wants to make sure that if the vase falls off the ledge, it won’t break. So he plans to purchase several identical vases and drop them out of the window to determine the highest floor he can live on without the vase breaking should it fall off the window ledge. Time is short, so Ryan would like to minimize the number of drops he has to make. 

Suppose that one vase was purchased and the building was 100 stories. If it was dropped out of the first floor window and broke, Ryan would live on the first floor. However if it did not break, it would have to be dropped from all subsequent floors until it broke. So the worst case minimum number of drops for one vase (V=1) and an N story building is always N drops. It turns out that if Ryan’s drop scheme is used, the worst case minimum number of drops falls off rapidly as the number of vases increases. For example, only 14 drops are required (worst case) for a 100 story building if two (V = 2) vases are used, and the worst case number of drops decreases to 9 if three vases are used. 

Your task is to discover the optimum drop algorithm, and then code it into a program to 
determine the minimum number of drops (worst case) given the number of vases Ryan purchased, V, and the number of floors in the building, N. Assume that if a vase is dropped and it does not break, it can be reused. 

Inputs: (from a text file)
The first line of input contains the number of cases to consider. This will be followed by one line of input per case. Each line will contain two integers: the number of vases Ryan purchased, V, followed by the number of stories in the building, N. N &lt; 1500 and V &lt; 200

Output: (to console)
There will be one line of output per case, which will contain the minimum number of drops, worst case. 

Sample Input 

   5 
   2 10 
   2 100 
   3 100 
   25 900 
   5 100 


Sample Output  (1 for each input) 

    4 
    14 
    9 
    10 
    7
I solved this in excel, as my work machine doesn't have any languages on it. obviously the input/output part doesn't quite match the question... so psuedocode answer :

Setup

Array Heights[200][1500]

for v = 1 to 200
  Heights[v][1] = 1
for d = 1 to 1500
  Heights[1][d] = d
for d = 2 to 200
  for d = 2 to 1500
    Heights[v][d] = Heights[v-1][d-1] + Heights[v][d-1] + 1


'Heights' now contains all the answers within range. (sort of)

Solutions

for each input (V,N) :
d = 1
while (d &lt;= 1500) and (Heights[V][d] &lt; N)
  d++
print d


A few notes:


if speed is vital the search in the 'solution' part can be replaced with a binary search
because of the 1500 limit on floors, you never need to consider more than 11 vases. (in fact if V > log2(N+1), then answer is just round up log2(N+1) )  ((ie binary vase drop search))
There is slight ambiguity in the question regarding the first floor. It says 'if it breaks on the 1st floor, he will live on the 1st floor' which leads to 'if it breaks on the 2nd floor, he will live on the 1st floor regardless of whether or not it breaks on the 1st'...