1993. Взвешивания

Дано n шариков. Из них n – 1 имеют одинаковый вес, а один шарик тяжелее остальных. Определите минимальное количество взвешиваний на весах с двумя чашами (без гирь), достаточное для нахождения тяжелого шарика.

Взвешивание выполняется следующим образом: на каждую чашу весов кладётся одинаковое количество шариков. Если одна чаша перевешивает другую, тяжелый шарик находится на более тяжелой чаше. Если же чаши уравновешены, тяжелый шарик среди шариков, не участвовавших во взвешивании. После каждого взвешивания вы самостоятельно выбираете, какие шарики будут участвовать в следующем взвешивании.

Вход. Одно целое число n (2 ≤ n ≤ 10⁹) – количество шариков.

Выход. Выведите минимальное количество взвешиваний, необходимое для определения тяжелого шарика.

Пример входа 1	Пример выхода 1
2	1
Пример входа 2	Пример выхода 2
4	2

РЕШЕНИЕ

функции

Анализ алгоритма

Разобьём все шары на три группы, по возможности одинаковые по количеству. Если число n не делится на 3, то размеры групп будут отличаться не более чем на один шар. Две группы одинакового размера положим на чаши весов. В результате одного взвешивания мы определим, в какой из трёх групп находится тяжёлый шар.

Таким образом, за одно взвешивание задача с n шарами в худшем случае сводится к задаче с шарами. Следовательно, для гарантированного обнаружения тяжёлого шара достаточно взвешиваний.

Второе решение. Пусть 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);

Реализация с проверкой на корректность входных данных

#include <stdio.h>

#include <math.h>

int n, res;

int main(void)

{

scanf("%d",&n);

try

{

if (n < 2) throw "n is less than 2";

if (n > 10) throw "n is greater than 10";

res = log(1.0*n) / log(3.0) + 1 - 1e-7;

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

}

catch (const char* msg)

{

puts(msg);

}

return 0;

}

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))))