Guess the Number

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

You friend is thinking of a number between l and r, and you are trying to guess it in as few guesses as possible. In response to each of your guesses, they will respond "HIGHER", "LOWER", or "CORRECT". You are required to find the number with at most \lceil \log_2{\left(l-r+1\right)} \rceil guesses.

Interaction

The first line of input contains integers l and r, the range of valid numbers. You may now make guesses by printing an integer. In response to each of your guesses, the judge will respond with a line containing HIGHER, LOWER or CORRECT which you can read as a line of input.

Example

The judge first inputs

1 10

Your program prints 5.

LOWER

Your program prints 4

CORRECT

Constraints

  • 1 \le l \le r \le 10^9

Template

l,r = (int(x) for x in input().split())

while True:
    print(guess)
    response = input()

    # Process response

    if response == "CORRECT":
        break

Comments

There are no comments at the moment.