|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||256 MB||1||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.
|Guess(5)||0||Same (first call)|
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)