2
\$\begingroup\$

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 < 1500 and V < 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
\$\endgroup\$
  • 3
    \$\begingroup\$ This is a site for hosting contests, not really a site for discussing contests. You need some way to decide a winner. Since the puzzle is fairly well known and the optimal solution is quite simple, I suspect that the best one would be code-golf: the shortest code wins. But in that case you need to clarify whether you require submissions to be programs which read from stdin and write to stdout or whether they can be functions or even blocks of code which assume the input in certain variables and leave the output in others. \$\endgroup\$ – Peter Taylor Jul 24 '14 at 21:35
  • \$\begingroup\$ I will edit the question. This is a well known problem? Can you provide some references? \$\endgroup\$ – Thorn Jul 24 '14 at 21:52
  • \$\begingroup\$ stackoverflow.com/q/3974077/573420 , acm.timus.ru/problem.aspx?space=1&num=1223 , code.google.com/codejam/contest/dashboard?c=32003#s=p2 , stackoverflow.com/q/4699067/573420 (ah, that's where I saw this before. I knew I remembered solving it) \$\endgroup\$ – Peter Taylor Jul 24 '14 at 21:57
  • \$\begingroup\$ Excellent. Thank you for the reference. I would say that the problem with 2 vases (or cats or eggs) is well known, but the generalization is less common. In any case, you gave a nice solution on SO. It looks like all solutions I've seen followed by solution path of first computing the maximal floor for a given number of vases and drops. \$\endgroup\$ – Thorn Jul 24 '14 at 22:06
  • \$\begingroup\$ I think the answer is the regular r-polytopic number, where n=vases and r=drops, with the lowest r, whose value is greater than the number of floors. mathworld.wolfram.com/FigurateNumber.html \$\endgroup\$ – isaacg Jul 24 '14 at 22:27
2
\$\begingroup\$

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 <= 1500) and (Heights[V][d] < 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'...
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.