E - デフレゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点： 500 点

問題文

RZK 君はお金に困っている. ある日, RZK 君はお金がもらえる以下のようなゲームを見つけた.

  • 1 以上 n 以下の目がすべて等確率に出る n 面体のサイコロがある.
  • プレイヤーは, 前に出したことのある面をもう一回出すまでサイコロを振り続けることができる. プレイヤーは, a の目を出すと a 円もらえるが, 前に出したことのある面を出したときにはお金はもらえない.
  • 例えば, プレイヤーが 1 -> 5 -> 3 -> 5 という順に面を出した場合, 1 + 5 + 3 = 9 円プレイヤーがもらえる.

RZK 君はそのゲームがすごく魅力的に見えたが参加費がとても高いので, ゲームで得られる金額の期待値を求めてから参加を検討しようと思った.

そのとき, このゲームでもらえるお金の期待値を求めよ.

入力

入力は以下の形式で標準入力から与えられる.

n

出力

このゲームでもらえるお金の期待値を出力せよ. 絶対誤差または相対誤差が 10^{-7} 未満であれば, 正解となる.

制約

  • n は 1 以上 500 \ 000 以下の整数である.

小課題

小課題1 [ 60点 ]

  • n \leq 8.

小課題2 [ 120点 ]

  • n \leq 18.

小課題3 [ 320点 ]

  • 追加の制約はない.

入力例1

2

出力例1

2.25000000000000

1円もらえる確率が 0.25, 2円もらえる確率が 0.25, 3円もらえる確率が 0.5 なので、もらえる金額の期待値は 2.25 である.

入力例2

6

出力例2

9.71141975308642

writer: Ryo2016