YL
BAN USER@jack, great solution! though I had 3 questions:
1) Shouldn't it be p = a/n and 1-p = b/n, with n = a + b.
2) shouldn't it be "if x < a: return head " instead of "if x < p: return head", because a is an integer and p is presumably a rational number?
3) shouldn't it be "x < n" or "x <= n-1" instead of "x <= n", because x could potentially take on n values, i.e., 0, 1, 2, 3, ... n - 1, right?
@rahul I agree with you the xa yb xy xy case cannot be resolved in 6 steps following the OP's approach.
Let me propose something else. If all four groups turn out to be not equal, then we have:
(1) xy xy xy ab or (2) xa yb xy xy
Next, let us throw away the heavier ball from each group, then we have 4 balls remaining and they could be:
(1) min(x,y) min(x,y) min(x,y) min(a,b)
or
(2) min(x,a) min(y,b) min(x,y) min(x,y)
Now split the 4 balls into two groups (with 2 balls per group) and compare. There are three possibilities:
(i) min(x,y) + min(x,y) vs. min(x,y) + min(a,b)
(ii) min(x,a) + min(y,b) vs. min(x,y) + min(x,y)
(iii) min(x,a) + min(x,y) vs. min(y,b) + min(x,y)
It is not hard to show that the lightest ball (our target) must be on the lighter side of the scale. We can resolve the two candidates by using one comparison.
For example, if we had (i) min(x,y) + min(x,y) vs. min(x,y) + min(a,b) in the previous step, and the LHS is lighter. That implies min(x,y) < min(a,b). Now we compare the two balls min(x,y) and min(x,y) from the LHS, and they turn out to be equal, so we return either one as our result.
"The line will be like BABABA...BA*,then A move,B jump n-1 times" — how does B jump n - 1 times? if A moves, the lines will become BABABA...B*A. I don’t see how B can jump n - 1 times after A moves. Could you explain?
- YL September 02, 2019