Зважування (Розбір)

Розіб'ємо всі кулі на три групи, по можливості однакові за кількістю. Якщо число $n$ не ділиться на $3$, то розміри груп відрізнятимуться не більше ніж на одну кулю. Дві групи однакового розміру покладемо на шальки терезів. В результаті одного зважування ми визначимо, в якій з трьох груп знаходиться важка куля.

Таким чином, за одне зважування задача з $n$ кулями у найгіршому випадку зводиться до задачі з $\lceil n/3\rceil$ кулями. Отже, для гарантованого виявлення важкої кулі достатньо ⌈log_3n⌉ зважувань.

Друге рішення. Нехай $p$ — найбільший степінь, для якої виконується нерівність 3^p < n. Тоді мінімальна кількість зважувань, необхідна для гарантованого виявлення важкої кулі, дорівнює p + 1.

Приклад

Для трьох куль достатньо одного зважування. Якщо шальки терезів знаходяться у рівновазі, то більш важка куля не була поміщена на терези.

У випадку $9$ куль розіб'ємо їх на $3$ групи по $3$ кулі. Помістивши по одній групі на кожну шальку терезів, за одне зважування ми визначимо, в якій групі знаходиться важка куля.

Якщо ж є $8$ куль, розіб'ємо їх на три групи наступним чином: $3,3$ і $2$ кулі. При цьому на шальки терезів покладемо дві групи по $3$ кулі.

Реалізація алгоритму

Читаємо кількість кульок $n$.

scanf("%d",&n);

Вичисляємо і виводимо відповідь.

res = ceil(log(n) / log(3));
printf("%.0lf\n",res);  

Реалізація алгоритму – циклічна

Читаємо кількість кульок $n$.

scanf("%d",&n); 

Вичисляємо і виводимо відповідь.

res = 0; p = 1;
while (p < n)
{
  p = p * 3;
  res++;
}

printf("%d\n",res);  

Java реалізація

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 реалізація

Читаємо кількість кульок $n$.

n = int(input())

Вичисляємо і виводимо відповідь.

print(int(math.ceil(math.log(n) / math.log(3))))