Взвешивания

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

Технические условия

Входные данные

В первой строке входного файла содержатся одно целое n (2 ≤ n ≤ 10).

Выходные данные

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 11.1111
Сложность: 2% 197/202

Пример

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

Sample 1
2

Sample 2
3

Sample 3
4

Sample 4
9

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

Sample 1
1

Sample 2
1

Sample 3
2

Sample 4
2

Список задач