atcoder#AGC044E. [AGC044E] Random Pawn
[AGC044E] Random Pawn
配点 : 点
問題文
あなたの目的は、これからプレイするゲームでの利得の期待値を最大化することです。 ゲームを開始すると、ポーン (チェスの駒) が から等確率に選ばれた位置 に置かれます。これらの 個の位置 は円周上に時計回りに並び、位置 の両隣は位置 です。
ゲームはターン制で進行します。各ターンでは、ゲームを終えて ドル ( はその時点でのポーンの位置) を得るか、 ドルを支払ってゲームを続けるかを選べます。 ゲームを続ける場合、ポーンは自身と隣接する つの位置 , のいずれかに等確率で移されます (位置 は位置 と、位置 は位置 とみなします)。
最適な戦略の期待利得は何ドルでしょうか。
注記: 「最適な戦略の期待利得」は、ゲームが 有限の ターン数で終わるような戦略における期待利得の上限と定義されます。
制約
- ()
- ()
- 入力中のすべての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
出力
最適な戦略の期待利得を 個の実数として出力せよ。
出力された値は、絶対誤差または相対誤差が を超えなければ正解とみなされる。
5
4 2 6 3 5
1 1 1 1 1
4.700000000000
4
100 0 100 0
0 100 0 100
50.000000000000
14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4
7047.142857142857
10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61
815899161079.400024414062