34212번 - Boring Game 점수다국어언어 제한함수 구현

문제

Alice and her little brother, Bob are playing a number guessing game.

Bob has selected a (hidden) integer $S$.

Alice can ask questions about the hidden number, which are of the following form: "Is the hidden number at least $x$?" Bob answers her questions with "Yes" or "No". Unfortunately, after $K ≥ 1$ questions, Bob gets bored of the game, and from then on, he will give false answers to all questions.

That is, Bob:

• Answers "Yes" to the first $K$ questions if and only if $x ≤ S,ドル and
• After the $K$-th question, he answers "Yes" if and only if $S < x$.

Note that Bob always answers correctly to the first question and Alice does not know the value of $K$.

Your task is to devise and implement a questioning strategy for Alice to identify the hidden number. Your score is based on the number of questions asked - the fewer questions, the better the score.

구현 상세

You should implement the following procedure.

long long play_game()

• This procedure is called at most $T$ times for each test case.

The procedure should find and return the hidden number $S$ by making calls to the following procedure to ask questions about the hidden number:

bool ask(long long x)

• $x$: the number specifying a question of Alice.
• The value of $x$ must be between 1ドル$ and 10ドル^{18},ドル inclusive.
• The procedure returns a boolean value representing Bob's answer.
• The procedure can be called at most 150ドル$ times in each call to play_game.

The behaviour of the grader is adaptive, meaning that in certain tests, the values of $S$ and $K$ are not fixed before play_game is called. It is guaranteed that there exists at least one $(S,K)$ pair for which the grader's answers are consistent.

입력

출력

제한

• 1ドル ≤ T ≤ 1000$
• 1ドル ≤ S ≤ 10^{18}$
• 1ドル ≤ K ≤ 150$

점수

If your solution does not adhere to the implementation details described above, or if the value returned by play_game is incorrect for even a single call, your solution will receive a score of 0ドル$.

Otherwise, let $C$ be the maximum number of questions your solution asks across all calls to play_game. Your score is calculated according to the following table:

예제

Consider a scenario where the hidden integer is $S = 2,ドル and $K = 1$. The game begins with the call:

play_game()

Suppose that play_game first calls ask(2). As 2ドル ≤ S = 2$ and Bob is telling the truth at this point, the call returns true.

Suppose play_game calls ask(2) again. Although the condition 2ドル ≤ S = 2$ still holds, but Bob is now lying (having already told the truth $K = 1$ time), so the call returns false. Receiving contradictory answers to the same question reveals that Bob will lie on all subsequent responses.

Now suppose play_game calls ask(3). Since 3ドル ≤ S = 2$ is false, and Bob is lying, the call returns true. At this point, we can deduce that 2ドル ≤ S < 3,ドル which implies $S = 2$.

Therefore, the procedure should return 2ドル$.

샘플 그레이더

The sample grader is not adaptive. It processes $T$ scenarios, and in each case reads fixed values of $S$ and $K$ from the input and answers questions accordingly.Input format:

T
S[0] K[0]
S[1] K[1]
...
S[T-1] K[T-1]

Here, $S[i]$ and $K[i]$ (0ドル ≤ i < T$) specify the hidden parameters for each call to play_game.

Output format:

G[0] C[0]
G[1] C[1]
...
G[T-1] C[T-1]

Here $G[i]$ (0ドル ≤ i < T$) is the number returned by play_game when the hidden parameters are $S[i]$ and $K[i],ドル and $C[i]$ is the number of questions asked during that call.

힌트

첨부

• boringgame.zip