B問題 - Hiyoko Checker

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

A君は4級ひよこ鑑定士です。彼の生業はひよこと鶏を区別することです。彼は見た目だけでは鶏とひよこを区別することができませんが、凄腕鑑定士のため、「鶏はひよこより重く、ひよこ同士、鶏同士はまったく同じ重さであること」を知っています。

彼はその区別のために天秤を使い重さを比較します。天秤では、好きな数のひよこと鶏からなる集団\(2\)つを乗せることで、そのどちらが重いか、あるいは同じ重さかを判定することができます。 (この天秤はどれだけひよこや鶏を乗っけても壊れない優れものです。)

さて、A君は\(N-1\)匹のひよこと1匹の鶏が紛れ込んだ集団の中からどれが鶏かを区別する依頼を受けました。A君が最適な方法をとった場合、最短で\(M\)回の天秤の使用で確実にこの中から鶏を見つけることができるとするとき、\(M\)を求めてください。

制約

• \(1 \leq N \leq 10^9\)
• \(N\)は整数として与えられる。

入力

N

標準入力に整数\(N\)が\(1\)行で与えられる。

出力

M

最短の操作回数\(M\)を\(1\)行に出力せよ。

入力例1

8

出力例1

2

必ず\(2\)回で操作が終了します。 まず、\(3\)匹と\(3\)匹をとり、天秤にかけます

1. 傾いた時

   傾いた方の\(3\)匹から\(2\)匹を取り出し、それぞれ\(1\)匹ずつ右と左の天秤にかけます。もし傾いたら、傾いた方にいたのが鶏ですし、そうでなければ残りの\(1\)匹が鶏です。

2. 傾かなかったとき

   残りの\(2\)匹を天秤にかけ、重かった方が鶏です。