828. Counting the Guesses
A referee picks a whole number h somewhere in 1 .. n and you have to name it. After each
guess the referee says "too low", "too high" or "correct". You will use this strategy, and no
other:
lo = 1, hi = n
repeat:
g = lo + (hi - lo) / 2 integer division, rounding down
announce g
if g == h: stop
if g < h: lo = g + 1 the referee said too low
else: hi = g - 1 the referee said too high
You are told n and h up front. Print how many guesses the strategy makes, and then the
guesses themselves in the order they are announced.
n = 10, h = 7 -> 4 guesses: 5 8 6 7
n = 7, h = 4 -> 1 guess: 4
n = 8, h = 1 -> 3 guesses: 4 2 1
## Why this is worth writing out
Every other problem in this block hides the search inside a solution and only shows you the
answer. Here the search IS the answer, so a single misplaced + 1 changes the output instead of
quietly changing nothing, and you find out immediately.
Two details are pinned by the statement and both are load bearing.
First, the midpoint rounds DOWN. With lo = 1 and hi = 2 the guess is 1, not 2. A strategy
that rounds up is just as good at finding the number and produces a different list, which is why
the statement fixes one.
Second, the guess is written lo + (hi - lo) / 2 and not (lo + hi) / 2. With n as large as
10^9 the two agree in exact arithmetic, but in a 32-bit signed integer lo + hi reaches
2 * 10^9, which is close enough to the ceiling of 2147483647 that the very last step on
n = 10^9 and h = 10^9 is already at 1999999999. Push n a little higher and it wraps.
hi - lo is never larger than n, so the pinned form cannot overflow at all.
## The invariant the strategy maintains
> h lies in [lo, hi].
True at the start because 1 <= h <= n. The referee's answer is what preserves it: "too low"
rules out everything at or below g, and "too high" rules out everything at or above g, so
each branch discards exactly the part that cannot contain h.
This is the one shape in the block that may write hi = g - 1 rather than hi = g. It is
allowed here precisely because the referee has already told you that g is not the answer. In
a lower-bound search no such promise exists, mid may be the answer, and hi = mid - 1 loses
it.
## Why it terminates
The range starts with n candidates and each guess removes at least half of them, since g
sits in the middle and is itself discarded. So the strategy finishes in at most
floor(log2(n)) + 1 guesses, which is 30 for n = 10^9. It never fails to find h, because
the invariant keeps h inside a range that only ever shrinks, and a range of one element must
be h itself.
## Related problems
Problem 559 asks a different question about the same game: what the guessing would COST in the worst case if a wrong guess were charged its own value. That is an optimisation over strategies and is solved with dynamic programming, not a search. This problem fixes one strategy and simply runs it.
## Cost
Time O(log n). Space O(log n) for the list of guesses.
Constraints - `1 ≤ h ≤ n ≤ 1000000000`
Input
A single line with two integers n and h: the largest number the referee may have picked and the number actually picked.
Output
Print two lines. The first is one integer, the number of guesses the strategy makes. The second is those guesses, in announcement order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.