A festival string has n bulbs, numbered 1..n, and exactly two of them are dead. A tester
clipped onto the string can check any stretch of consecutive bulbs: any_dead(a, b) reports
True if at least one dead bulb is among bulbs a..b (inclusive).
Write find_dead(n, any_dead) that returns the numbers of the two dead bulbs as a tuple
(first, second) with first < second. You may use the tester at most 2 * ⌈log2(n - 1)⌉
times; one test too many raises TooManyTests.
The tests run with_tester(find_dead, n, seed), which hides the two dead bulbs and counts your
tests. Try it with Run: print(with_tester(find_dead, 50, 1)).
Examples
Input: with_tester(find_dead, 9, 1) (9 bulbs: at most 2 * 3 = 6 tests)
Output: {"answer": ..., "tests": ..., "limit": 6, "dead": ...}
correct when answer == dead
Input: with_tester(find_dead, 2, 2) (both bulbs are dead; no test is needed)
Output: {"answer": (1, 2), "tests": 0, "limit": 0, "dead": (1, 2)}
Constraints
2 <= n <= 10**9- at most
2 * ⌈log2(n - 1)⌉tests any_dead(a, b)raisesValueErrorunless1 <= a <= b <= n
Goals
- Find several hidden items with questions about whole groups
- Use what one search found to shrink the next search