Problem D

Breaking Level

Source file: n:\d\d.{c, cpp, pas}

You are playing a game with your friends up in a tall tower with N levels labelled 1 to N (1 <= N <= 100). You are given a 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 <= H <= 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 interact with a provided library named level. The library has four operations:

GetD and GetN. Each of these should be called once at the beginning of the simulation. They return the value of D and N respectively.
Drop(t), called with an integer argument, simulates the dropping of a sample from level t. It returns 1 if the sample breaks; it returns 0 otherwise.
Decide(t) 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.

Testing Your Program

The library reads the values of N, D, and H (in that order) from the file named level.in. You can modify the values in this file in order to test your program. After the simulation has finished, the library outputs two files. The first file, named level.out, contains the integer that your program passed to the Decide routine. The other file output by the library is a log file, level.log, describing the calls that your program made to the library routines.

Example

contents of level.in:
5 3 2

possible sequence of library calls:

GetN returns 5.
GetD returns 3.
Drop(3) returns 1.
Drop(1) returns 0.
Drop(2) returns 1.
Decide(2)

Instructions for Pascal Programmers

To access the library, your program must contain the statement

uses level;

For your information, here are the function and procedure declarations:

function GetN:integer ;
function GetD:integer ;
function Drop( level:integer ) : integer ;
procedure Decide( level:integer ) ;

Instructions for C/C++ Programmers

Use the instruction

#include "level.h"

in your source code. Create a project D.PRJ and add your file d.c (d.cpp) and the library level.obj to your project.
For your information, the function headers are:

int GetN( void ) ;
int GetD( void ) ;
int Drop( int level ) ;
void Decide( int level ) ;

Additional Information

Your program is not allowed to read from or write to any files.