問題一覧 > 通常問題

No.352 カード並べ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が10−6 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 88
作問者 : nmnmnmnmnmnmnm
3 ProblemId : 750 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-03-11 22:38:56

問題文

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

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

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

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

入力

N

Nは整数。2≤N≤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×2の2で確率は1/3である。
最右に置くコストは1で確率は1/3である。
よって、1+1+(1+2+1)×(1/3)より期待値は3.33333333となる。

サンプル3
入力
17
出力
365.8791050453

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。