Hotter Colder Interactive Compilation commands
Time limit | Memory limit | # of submissions | # of accepted | Ratio |
---|---|---|---|---|
10000 ms | 256 MiB | 641 | 8 | 1.25% |
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:
- hotter if this guess is closer to Jill's number than his previous guess
- colder if this guess is farther from Jill's number than his previous guess
- same if this guess is neither closer to nor further from Jill's number than his previous guess.
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.Call | Returned value | Explanation |
---|---|---|
Guess(5) | 0 | Same (first call) |
Guess(3) | 1 | Hotter |
Guess(4) | -1 | Colder |
Guess(1) | 1 | Hotter |
Guess(3) | 0 | Same |
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 2^{W}≤3N. For this subtask your solution will score:- 0 points, if HC(N) calls Guess(G) 2W times or more,
- 25α points, where α is the largest real number, such that 0<α<1 and HC(N) calls Guess(G) at most 2W-αW times,
- 25 points, if HC(N) calls Guess(G) at most W times.
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
- To be implemented by contestant: hottercolder.c or hottercolder.cpp or hottercolder.pas
- Contestant interface: hottercolder.h or hottercolder.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 input file contains several lines, each containing N and Jill's number. - Expected output for sample grader input: the grader will create files grader.out.1 grader.out.2 etc.
- If the implementation correctly implements Subtask 1, one line of output will contain OK 1
- If the implementation correctly implements Subtask 2, one line of output will contain OK 2
- If the implementation correctly implements Subtask 3, one line of output will contain OK 3
- If the implementation correctly implements Subtask 4, one line of output will contain OK 4 alpha α
File name | File size |
---|---|
hottercolder.zip | 8.3 MiB |