Bob was bored, so he challenged Alice to a guessing game. Bob starts with an integer , which Alice must try to guess. Every time that Alice guesses an integer , Bob reports the distance between and . Then, Bob performs the following modification to :
- First he sets to the midpoint of and , rounding to the integer closest to the value of
- Then, he tosses a fair coin, and if it lands tails, he reflects over
Alice would like you to help her come up with a strategy that minimizes the number of guesses that she has to make. To verify that the strategy that you came up with is reasonable, Alice will check that every guess that you make is between and (inclusive), where is the minimum value that can take given the current set of information, and is the maximum value.
Constraints
The initial value of satisfies .
You are allowed to make at most guesses.
Interaction
This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.
You will start the interaction by proceeding with your guesses. Each guess should be formatted as y
followed by a \n
character. In response, you will be given the current value of on its own line. If , then you have correctly guessed and you should immediately terminate your program. Otherwise, will be modified as stated above, and you should continue with the interaction.
If at any point you attempt an invalid question (such as an invalid output format or a prohibited value of ), or you exceed the limit of guesses, the interactor will respond with . You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict.
Please note that you may need to flush stdout
after each operation, or interaction may halt. In C++, this can be done with fflush(stdout)
or cout << flush
(depending on whether you use printf
or cout
). In Java, this can be done with System.out.flush()
. In Python, you can use sys.stdout.flush()
.
Scoring
If you fail to guess in at most guesses, or at any point output an invalid guess, then you will receive points. Otherwise, you will receive of the points for a correct guess, and of the points if you guessed in at most guesses.
Sample Interaction
>>>
denotes your output. Do not print this out.
>>> 3
2
>>> 4
0
Sample Explanation
The initial value of is , and the value after the first guess is . Therefore, the second guess is correct, and interaction terminates.
Comments