No.352 カード並べ
タグ : / 解いたユーザー数 87
作問者 :
nmnmnmnmnmnmnm
問題文
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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。