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