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

 

Дано n шаров, из них n – 1 шар имеет одинаковый вес, а один тяжелее. Требуется за минимальное количество взвешиваний на рычажных весах определить, какой из шаров является тяжёлым. Операция взвешивания заключается в том, что на каждую из двух чаш весов кладётся одинаковое количество шаров. Если какая-то чаша перевесила – тяжёлый шар среди положенных на неё. Если весы оказались в равновесии – тяжёлый шар среди не лежащих на весах шаров. После каждого взвешивания можно принять решение о том, какие шары будут участвовать в следующем взвешивании.

 

Вход. Одно целое число n (2 ≤ n ≤ 109).

 

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

 

Пример входа 1

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

2

1

 

 

Пример входа 2

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

4

2

 

 

РЕШЕНИЕ

функции

 

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

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

Второе решение. Пусть p – максимальная степень, для которой 3p < n. Тогда наименьшее количество взвешиваний для гарантированного обнаружения тяжёлого шара равно p + 1.

 

Пример

Для трех шаров достаточно одного взвешивания. Если чаши весов будут в равновесии, то более тяжелый шар находится не на весах.

В случае 9 шаров разложим их на 3 кучки по 3 шара. Положив на чаши весов по одной кучке, за одно взвешивание мы определим кучку в которой находится тяжелый шар.

Если имеется 8 шаров, то разложим их на три кучки следующим образом: 3, 3, 2. При этом на чаши весов положим кучки 3 и 3.

 

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

По заданному целому числу n вычисляем и выводим действительное значение . Операция округления вверх возвращает значение double. Результат выводим без десятичных цифр – в таком случае он округляется до ближайшего целого.

 

scanf("%d",&n);

res = ceil(log(1.0*n) / log(3.0));

printf("%.0lf\n",res); 

 

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

 

#include <stdio.h>

#include <math.h>

 

int n, p, res;

 

int main(void)

{

  scanf("%d",&n);

  res = 0; p = 1;

  while(p < n)

  {

    p = p * 3;

    res++;

  }

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

  return 0;

}

 

 

Реализация Visual Studio 2013 / 2015

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <math.h>

 

int n, res;

 

int main(void)

{

  scanf("%d",&n);

  res = ceil(log(n) / log(3));

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

  return 0;

}

 

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

 

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

 

import math

n = int(input())

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