Day 1 Task 2: Hotter Colder

Jack and Jill play a game called Hotter, Colder. Jill has a number between 1 and N, and Jack makes repeated attempts to guess it.

Each of Jack's guesses is a number between 1 and N. In response to each guess, Jill answers hotter, colder or same. For Jack's first guess, Jill answers same. For the remaining guesses Jill answers:

You are to implement a procedure HC(N) that plays Jack's role. This implementation may repeatedly call Guess(G), with G a number between 1 and N. Guess(G) will return 1 to indicate hotter, -1 to indicate colder or 0 to indicate same. HC(N) must return Jill's number.

Example

As example, assume N=5, and Jill has chosen the number 2. When procedure HC makes the following sequence of calls to Guess, the results in the second column will be returned.
CallReturned valueExplanation
Guess(5)0Same (first call)
Guess(3)1Hotter
Guess(4)-1Colder
Guess(1)1Hotter
Guess(3)0Same
At this point Jack knows the answer, and HC should return 2. It has taken Jack 5 guesses to determine Jill's number. You can do better.

Subtask 1 [25 points]

HC(N) must call Guess(G) at most 500 times. There will be at most 125 250 calls to HC(N), with N between 1 and 500.

Subtask 2 [25 points]

HC(N) must call Guess(G) at most 18 times. There will be at most 125 250 calls to HC(N) with N between 1 and 500.

Subtask 3 [25 points]

HC(N) must call Guess(G) at most 16 times. There will be at most 125 250 calls to HC(N) with N between 1 and 500.

Subtask 4 [up to 25 points]

Let W be the largest integer, such that 2W≤3N. For this subtask your solution will score:

There will be at most 1 000 000 calls to HC(N) with N between 1 and 500 000 000.

Be sure to initialize any variables used by HC every time it is called.

Implementation Details