How Many Rounds Before You Look?

Grover's search on N = 2^n items, M of them marked (their indices are in marked):

• Start with every amplitude equal to 1/\sqrt{N}.
• One round: the phase oracle multiplies the amplitude of item x by (-1)^{f(x)}, with f(x) = 1 exactly for the marked items (the marked amplitudes change sign); then every amplitude a becomes 2m - a, where m is the mean of all N amplitudes after the marking.
• The success probability p_k after k rounds is the sum of |a_x|^2 over the marked items: the chance that measuring the chip then shows a marked item.

A popular rule of thumb says to run

rounds (in Python math.floor(math.pi / 4 * math.sqrt(N / M))). Check it. Write best_rounds(n, marked, K) that returns a pair (best, rule):

• best is the number of rounds k in 0, 1, \dots, K with the highest p_k. Ties: if several k have p_k within 1e-9 of the highest value, return the smallest of them.
• rule is k_{\text{rule}} as defined above (it may be larger than K).

Examples

Input:  n = 2, marked = [3], K = 3
Output: (1, 1)
Explanation: p = [0.25, 1.0, 0.25, 0.25]; the rule agrees.

Input:  n = 7, marked = list(range(19)), K = 3
Output: (1, 2)
Explanation: p is about [0.1484, 0.8595, 0.8435, 0.1328]: the rule runs one round too many.

Input:  n = 2, marked = [0, 2], K = 2
Output: (0, 1)
Explanation: with half of the items marked, p = [0.5, 0.5, 0.5]: a tie, so the smallest k wins.

Constraints

• marked holds at least one index

Goals

• Find the number of Grover rounds that maximises the success probability
• Compare it with the rule of thumb floor(pi/4 * sqrt(N/M))
• Notice when the rule of thumb is wrong, in particular when most items are marked