1993. Weighing
Given n balls. Among them, n – 1 have the same
weight, and one ball is heavier than the others. Determine the minimum number
of weighings on a two-pan balance (without weights) required to find the heavy
ball.
A weighing is
performed as follows: the same number of balls is placed on each pan of the
balance. If one pan is heavier than the other, the heavy ball is on the heavier
pan. If the pans balance, the heavy ball is among the balls that were not
placed on the balance. After each weighing, you choose which balls will
participate in the next weighing.
Input. One integer n (2 ≤ n ≤ 109)
– the number of balls.
Output. Print the minimum number
of weighings required to identify the heavy ball.
|
Sample
input 1 |
Sample
output 1 |
|
2 |
1 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
4 |
2 |
SOLUTION
mathematics
Algorithm analysis
Divide all the balls into
three groups that are as equal in size as possible. If the number n is not divisible by 3, the sizes of the groups
will differ by at most one ball. Two groups of equal size are placed on the
pans of the balance. As a result of one weighing, we determine in which of the
three groups the heavy ball is located.
Thus, after one weighing,
the problem with n balls is reduced in the worst case to a problem with 
balls. Therefore, 
weighings are sufficient to guarantee the detection of the
heavy ball.
Second solution. Let p be the largest exponent
for which the inequality 3p
< n holds. Then the minimum number
of weighings required to guarantee the detection of the heavy ball is p + 1.
Example
For 3 balls, a single
weighing is sufficient. If the pans of the balance are in equilibrium, then the
heavier ball was not placed on the balance.
In the case of 9 balls, we
divide them into 3 groups of 3 balls each. By placing one group on each pan of
the balance, a single weighing allows us to determine which group contains the
heavy ball.
If there are 8 balls,
divide them into three groups as follows: 3, 3, and 2 balls. In this case, the
two groups of 3 balls are placed on the pans of the balance.
Algorithm implementation
Read the number of balls n.
scanf("%d",&n);
Compute and print the answer.
res =
ceil(log(n) / log(3));
printf("%.0lf\n",res);
Algorithm implementation – loop
Read the number of balls n.
scanf("%d",&n);
Compute and print the answer.
res = 0; p = 1;
while
(p < n)
{
p = p * 3;
res++;
}
printf("%d\n",res);
Java implementation
import java.util.*;
public class Main
{
public static void main(String []args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
double res = Math.ceil(Math.log(n) / Math.log(3));
System.out.printf("%.0f\n",res);
con.close();
}
}
Python implementation
Read the number of balls n.
n = int(input())
Compute and print the answer.
print(int(math.ceil(math.log(n) / math.log(3))))