No.352 カード並べ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下
タグ : / 解いたユーザー数 59
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
1 ProblemId : 750 / 出題時の順位表

問題文

1からNまでの数字が書かれたカードが各1枚、合計N枚渡される。
まずA君はコスト1で1のカードを置く。
さらにA君は数字の小さいカードから順に横1列にカードを並べていく。

すでに置かれているカードが$M$枚の場合
次のカードの置きかたは、「最左」もしくは「最右」、「いずれかのカードとカードの間に入れて置く」の$M+1$通りで、
それぞれ$\frac{1}{M+1}$の確率で偏りなくランダムに選ばれる

カードの置かれ方によりコストが異なる。
・すでにある列の最左もしくは最右に置かれる場合、そのコストは1である。
・すでにあるいずれかのカードとカードの間に入れて置かれる場合、そのコストは置くカードの両隣のカードの数の積である。

A君が1のカードからカードを並べて置いていくとき、
最後のN枚目を置き終わるまでにかかったコストの和の期待値を求めよ。

入力

N

Nは整数。$2\le N \le 20$。

出力

期待値を1行で出力せよ。
なお許容誤差は1e-06である。
最後に改行を忘れずに。

サンプル

サンプル1
入力
2
出力
2.0000000000

最初の1のカードを置くコストが1である。
次に2のカードを置くコストは1のカードの左右どちらに置いても1である。
よって、2つのカードを置くコストの期待値は2である。

サンプル2
入力
3
出力
3.3333333333

最初の1のカードを置くコストが1である。
次に2のカードを置くコストは1である。
次に3のカードを置く時、最左に置くコストは1で確率は1/3である。
1と2のカードの間に置くコストは$1\times2$の2で確率は1/3である。
最右に置くコストは1で確率は1/3である。
よって、$1+1+(1+2+1)\times(1/3)$より期待値は3.33333333となる。

サンプル3
入力
17
出力
365.8791050453

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。