A security lab tests an automated vault-cracking rig against a mechanical dial whose true combination is some integer setting between 1 and n. Before each attempt the rig maintains a search window [low, high]; it always starts with low = 1 and high = n. On every attempt it computes mid = low + (high - low) / 2 (integer division), dials in mid, and reads the vault's feedback: the setting mid is too low, too high, or it matches exactly. If mid is too low the rig narrows the window to [mid + 1, high]; if mid is too high it narrows to [low, mid - 1]; the process stops the instant mid equals the true combination.
You have the vault's true combination in hand from a prior teardown (this is a bench replay, not a live attack), along with n. Reconstruct the exact sequence of settings the rig would have dialed in, in the order it would have tried them.
A single line containing two integers n and target, separated by a space.
Print each attempted setting on its own line, in the order the rig would try it, ending with the line that equals target (that is always the final line printed).
1 <= target <= n <= 2147483647Example 1
Input
10 6
Expected
5 8 6
Explanation
low=1, high=10: mid = 1 + (10-1)/2 = 5, which is too low, so low becomes 6. Next mid = 6 + (10-6)/2 = 8, too high, so high becomes 7. Next mid = 6 + (7-6)/2 = 6, which equals the target and the process stops. The attempts in order are 5, 8, 6.
Example 2
Input
1 1
Expected
1
Explanation
low=1, high=1, so the only possible mid is 1, which immediately equals the target. Only one attempt is made: 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →