Guessing Game

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Bob was bored, so he challenged Alice to a guessing game. Bob starts with an integer x, which Alice must try to guess. Every time that Alice guesses an integer y, Bob reports the distance |x-y| between x and y. Then, Bob performs the following modification to x:

  • First he sets x to the midpoint of x and y, rounding to the integer closest to the value of y
  • Then, he tosses a fair coin, and if it lands tails, he reflects x over y

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 A and B (inclusive), where A is the minimum value that x can take given the current set of information, and B is the maximum value.

Constraints

The initial value of x satisfies 1 \leq x \leq 10^9.

You are allowed to make at most 30 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 |x - y| on its own line. If |x - y| = 0, then you have correctly guessed x and you should immediately terminate your program. Otherwise, x 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 y), or you exceed the limit of 30 guesses, the interactor will respond with -1. 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 x in at most 30 guesses, or at any point output an invalid guess, then you will receive 0 points. Otherwise, you will receive 50\% of the points for a correct guess, and 100\% of the points if you guessed x in at most 10 guesses.

Sample Interaction

>>> denotes your output. Do not print this out.

>>> 3
2
>>> 4
0

Sample Explanation

The initial value of x is 1, and the value after the first guess is 4. Therefore, the second guess is correct, and interaction terminates.


Comments

There are no comments at the moment.