Ben Toh

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

Problem F: Ben Toh

午後8時のスーパーマーケットには、今日も狼と呼ばれる者共が集っていた。彼らの求めるものはただ一つ、半額のラベルが貼られた弁当である。数少ないそれを奪い合って、彼らは毎日激しい戦いを繰り広げるのだ。そして最も腹の虫の加護を受けた者共は見事半額の弁当を手に入れ、そうでない者は泣く泣くどん兵衛でもすすることになるのである。

とある高校生・佐藤も、そんな狼の一人である。彼の住んでいる高校の寮では、夕食は支給されない。加えて両親からの仕送りも少ないので、彼は何としても半額弁当を手に入れて、小遣いを浮かせなければならない。そうでなければ、漫画やゲームの類を諦めるか、アルバイトを始めなければならなくなってしまうのだ。

佐藤は優秀な狼なので、最初の日は100%の確率で半額弁当を手に入れることができる。しかしその翌日は、他の多くの狼たちが結託して佐藤の邪魔をしようとするので、半額弁当の入手確率は50%に低下する。それでも手に入れることができたならば、その翌日はさらに激しい妨害を受け、入手確率は25%になる。以降も同様に、半額弁当を手に入れると、翌日の入手確率はその日の半分になっていく。一度半額弁当の入手に失敗すると、その翌日の入手確率はまた100%に戻る。

佐藤は n 日の間スーパーマーケットに通いつづけ、半額弁当を得ようとしている。消費計画を立てたい佐藤のために、彼が半額弁当を得られる回数の期待値を求めるプログラムを作成してほしい。

Input

入力は複数のデータセットから構成される。

1つのデータセットに対する入力は、1つの整数 n で与えられる。

n = 0 のとき入力の終了を示す。

Output

各データセットごとに、期待値を含む1行を出力せよ。小数点以下何桁でも表示して構わない。表示する答えは、 1.0e-2 未満の誤差を含んでいてもよい。

Constraints

  • 1 ≤ n ≤ 100,000

Sample Input

1
2
3
0

Output for the Sample Input

1.00000000
1.50000000
2.12500000

Source: University of Aizu Programming Contest , Aizu-Wakamatsu, Japan, 2010-05-29
Problem Setter:  Takashi Tayama