Problem 313145 · medium · Level 03 Linear Management & Searching

The Hollow Ring

ternary search · interactive · query limits · balance scale

A jeweller has n gold rings, numbered 1..n, in a row on the bench. They all weigh the same except one hollow fake, which is lighter. The only tool is a two-pan balance. A weighing puts the rings a..b on the left pan and the rings c..d on the right pan (both ranges inclusive, the same number of rings on each side, no ring on both pans) and reports

  • "left" if the left pan is lighter (the fake is among a..b),
  • "right" if the right pan is lighter (the fake is among c..d),
  • "equal" if the pans balance (the fake is on neither pan).

Write find_fake(n, weigh) that returns the number of the fake ring. Call weigh(a, b, c, d) for a weighing. You may weigh at most ⌈log3 n⌉ times; one weighing too many raises TooManyWeighings.

The tests run with_balance(find_fake, n, seed), which hides the fake and counts your weighings. Try it with Run: print(with_balance(find_fake, 100, 1)).

Examples

Input:  with_balance(find_fake, 9, 1)   (9 rings: at most 2 weighings)
Output: {"answer": ..., "weighings": ..., "limit": 2, "fake": ...}
        correct when answer == fake

Input:  with_balance(find_fake, 1, 2)   (a single ring is the fake; no weighing)
Output: {"answer": 1, "weighings": 0, "limit": 0, "fake": 1}

Constraints

  • 1 <= n <= 10**9
  • at most ⌈log3 n⌉ weighings (n <= 3**k needs at most k)
  • weigh raises ValueError if a range is empty, leaves 1..n, the pans hold different numbers of rings, or the ranges overlap

Goals

  • Use a question with three answers to cut the candidates into thirds
  • Prove a question limit of about log3(n)
Starting Python…