eolymp
bolt
Try our new interface for solving problems
Məsələlər

Взвешивания

Взвешивания

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

Giriş verilənləri

Одно целое число n (2n10^9).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
Çıxış verilənləri #1
1
Giriş verilənləri #2
4
Çıxış verilənləri #2
2
Giriş verilənləri #3
9
Çıxış verilənləri #3
2