Canadian Computing Competition: 2001 Stage 2, Day 2, Problem 1

You are playing a game with your friends up in a tall tower with $N$ levels labelled $1$ to $N$ $(1\le N\le 100)$. You are given an object which is somewhat fragile, and you are warned that the object will break if you drop it from the "breaking level" or higher. That is, for the given object, there is a unique level $H$ $(1\le H\le N)$ such that if the object is dropped from level $H-1$ or lower, it will not break, and if it is dropped from level $H$ or higher, it will break. Your job is to determine the breaking level by dropping samples of the object from various levels of the building and observing the results.

Your friends have made the challenge a bit harder. You are given only two samples of the object. Once these have broken, there are no more objects to drop. There is one more restriction: you are given only a certain number, $D$, of opportunities to drop the object ($D$ is much less than $N$). If you successfully determine the breaking level (the unique $H$ defined above) before you run out of drop opportunities and using no more than the $2$ samples of the object, you win the game and the unending respect and cash of your friends.

To simulate the dropping of the object from a level, your program will use an interactor. The interactor has four operations:

• GetD and GetN: Each of these should be called once at the beginning of the simulation and return the value of $D$ and $N$, respectively.

• Drop t: It simulates the dropping of a sample from level $t$. It returns 1 if the sample breaks; it returns 0, otherwise.

• Decide t: It should be called once at the end of the simulation. It indicates to the library that your program has determined that the breaking level is $t$. This routine also terminates your program.

Sample Interaction

>>> denotes your output; don't actually print this out.

>>> GetN
5
>>> GetD
3
>>> Drop 3
1
>>> Drop 1
0
>>> Drop 2
1
>>> Decide 2