시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 18 | 0 | 0 | 0.000% |
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.
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 |
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.
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.
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.
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.
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.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)