Guess the Number

Problem:
https://open.kattis.com/problems/guess

This is an interactive problem. The judge is thinking of a number between 1 and 1000, and you repeatedly print guesses. After each guess, the judge replies:

• lower (your guess was too high)
• higher (your guess was too low)
• correct (you found it)

The goal is to find the number in less than 10 guesses (the log of 1000) — perfect for binary search.

💡 Approach

Use classic binary search on the range:

• Start with l = 1, r = 1000
• Guess the middle: m = (l + r) // 2
• If response is:
  • lower → move the right bound: r = m - 1
  • higher → move the left bound: l = m + 1
  • correct → stop

Important interactive rules

• After printing a guess, you must flush output so the judge sees it immediately.
• Read the judge response after each guess.
• Stop right away when you receive correct.

Time complexity: O(log 1000)
Space complexity: O(1)

# 2.1 https://open.kattis.com/problems/guess
# interactive binary search

l = 1
r = 1000

while True:
    m = (l + r) // 2
    print(m, flush=True)

    response = input().strip()

    if response == "correct":
        break
    elif response == "lower":
        r = m - 1
    elif response == "higher":
        l = m + 1