Demonstration Task 1: Guess

Jill is thinking of a number between 1 and N, and Jack wants to guess it by asking Jill questions of the form "Is it bigger than K?" for K between 1 and N.

You are to implement a procedure play(N) that implements Jack's role in the game. Your implementation should repeatedly call the procedure bigger(K), which is implemented by the grader. bigger(K) will return 1 if Jill's number is greater than K; otherwise it will return 0. Jill's number should be returned by your implementation as the result of play.

Subtask 1 [50 points]

Assume that N=16. Your implementation must use at most 15 calls to bigger and must return the correct result. The implementation files described below contain a correct implementation of this subtask.

Subtask 2 [50 points]

Assume that N=16. Your implementation must use at most 4 calls to bigger and must return the correct result.

Implementation Details

• Use the RunC programming and test environment
• Implementation folder: /home/ioi2010-contestant/guess/ (download prototype here)
• To be implemented by contestant: player.c or player.cpp or player.pas
• Contestant interface: player.h or player.pas
• Grader interface: grader.h or graderlib.pas
• Sample grader: grader.c or grader.cpp or grader.pas and graderlib.pas
• Sample grader input: grader.in.1 grader.in.2
  Note: The sample grader reads N and Jill's number from standard input.
• Expected output for sample grader input: grader.expect.1 grader.expect.2
• Compile and run (command line): runc grader.c or runc grader.cpp or runc grader.pas
• Compile and run (gedit plugin): Control-R, while editing any implementation file.
• Submit (command line): submit grader.c or submit grader.cpp or submit grader.pas
• Submit (gedit plugin): Control-J, while editing any implementation or grader file.
• CPU time limit: 10 seconds
• Memory limit: 256 MB