Earth Invasion Diary of Miyabi-sensei

時間制限 : 8 sec, メモリ制限 : 65536 KB

Problem A: 雅先生の地球侵略日誌

クァークゴ帝国遠征軍は、地球侵略をもくろむ悪の組織である。彼らは侵略者の伝統にのっとり、日 本の東京周辺をターゲットに、毎週1体のペースで怪人を送りこみ続けていた。しかし、そのたびに 人類戦隊アースファイブと名乗る5人の戦士があらわれ、街で暴れまわっていた怪人はあっさりと倒 されてしまうのであった。

ワルザード・スルー(地球名:源雅)は、そんな現状を本気で憂いている、クァークゴ帝国遠征軍の 女幹部である。彼女は、毎週の敗北から何も学ぼうとしない司令官や、どこかズレた発明を繰り返す 天才科学者らの下で、頭の痛い日々を過ごしていた。

そんな中、次の作戦は吸血怪人ドラキュラスを日本に送りこむことに決まった。ドラキュラスは、血 を吸った人間をドラキュラスに変えてしまう恐るべき怪人である。ドラキュラスに血を吸われた人間 もまた、他の人間の血を吸って仲間のドラキュラスを増やしていく。こうして地球全土をドラキュラ スで埋めつくしてしまおうという作戦だ。

これを聞いたワルザードは、すぐに悟った。この作戦は、幼稚園バスの乗っ取りのような普段やって いるセコい作戦とは訳が違う。あのダメ司令官が立案したものにしては珍しく、本当に地球を征服で きる可能性を秘めていると。

倍々ゲームの勢いは恐ろしい。地上に降りたったドラキュラスは、またたく間に仲間の数を増やして いった。このまま行けば地球侵略は目と鼻の先だと思われた。だがその瞬間、ワルザードの脳裏を、 強烈にいやな予感が走り抜けた。まさか、この怪人、オリジナルが倒されると仲間も全滅するなんて ことはないよな?

慌ててドラキュラスを設計開発した科学者を問いつめたところ、やはりワルザードの危惧していた通 りだった。オリジナルのドラキュラスがやられると、血を吸われた人間はすべて元に戻るように設計 してあるのだという。ふざけんなよ開発者。どうしてそんな余計な機能をつけた!

ワルザードは、開発担当者に飛び膝蹴りをきめると、すぐさまオリジナルの回収作業にとりかかっ た。いくらオリジナルと偽物は見た目がまったく同じだといっても、このままでは、駆けつけたアー スファイブに何かしらの理由でオリジナルを見抜かれて敗北するのが目に見えている。

開発者の話によると、ドラキュラス化した人間の重さはすべて同じだが、オリジナルのドラキュラス はそれよりも少しだけ重いらしい。それならば、天秤ばかりを使えばオリジナルを見つけることがで きるはずだ。アースファイブがあらわれる前に、できるだけ早くオリジナルのドラキュラスを見つけ て回収しなければ。

Input

N

入力の1行目には、整数 N(2 ≤ N ≤ 2,000,000,000)が書かれている。これは、オリジナルと偽物を合わせたドラキュラスの数をあらわす。

Output

天秤ばかりを使ってN 体のドラキュラスの中から1体のオリジナルを見つけるには、最悪の場合で も天秤ばかりを何回使えれば十分か。その最小値を出力せよ。ただし、天秤ばかりの左と右の皿に、 それぞれ何体かのドラキュラスを乗せて重さを比較することを、1回とカウントする。

Sample Input 1

8

Sample Output 1

2

Sample Input 2

30

Sample Output 2

4

Sample Input 3

2000000000

Sample Output 3

20

Source: ACM-ICPC Japan Alumni Group Summer Camp 2010 , Day 2, Tokyo, Japan, 2010-09-18
http://acm-icpc.aitea.net/