A game server has picked a secret integer in 1..upper_bound. You can only learn about it through server.check(guess), and the server is one call behind: each call submits a new guess and returns the verdict on the guess you submitted on the previous call.
- The very first call returns
"PENDING"(there's no earlier guess yet). - Every later call returns, about the previous guess:
"TOO_LOW"(it was below the secret),"TOO_HIGH"(above), or"CORRECT". - Every guess must be an integer in
1..upper_bound; anything else raisesValueError.
Implement find_secret(upper_bound: int, server) -> int that returns the secret. You don't need to hear "CORRECT": once only one value is possible, just return it.
# secret = 6, upper_bound = 10
server.check(5) # "PENDING"
server.check(8) # "TOO_LOW" verdict on 5: the secret is in 6..10
server.check(6) # "TOO_HIGH" verdict on 8: the secret is in 6..7
server.check(7) # "CORRECT" verdict on 6
# find_secret returns 6 (it could also have stopped once only one value was left)
Call budget: at most ceil(1.45 * log2(upper_bound)) + 3 calls (for upper_bound = 10**9 that is 47), with upper_bound up to 10**12. The tests also play against an adversarial server that picks the secret as late as it can, so the budget must hold in the worst case.
The obvious fix, asking about each midpoint twice so you can wait for its verdict, costs two calls per halving (about 60 calls for 10**9) and blows the budget. So does always sending the next guess to the middle of one half: an adversary makes it land in the wrong half every time.
Show hint
While a guess g is waiting for its verdict, send the next guess into one side of g, so it's useful if the secret is on that side and wasted otherwise. Split unevenly: let F[c] be the largest range you can finish in c calls when a well-placed guess is already in flight, and E[c] the same with nothing useful in flight. Then E[c] = F[c - 1] and F[c] = F[c - 1] + 1 + E[c - 1]: the side that gets the next guess may be as large as F[c - 1], the other side only E[c - 1]. Place each guess so its two sides respect those sizes.