No.1501 酔歩

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 :

遭難者 / テスター :

nok0

10 ProblemId : 6270 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-05-08 01:20:03

問題文

$1$ から $N$ までの番号がついた $N$ 個のマスと $1$ つの駒があります。始め、駒はマス $K$ に置かれています。

各マスに整数が書かれており、マス

i

には

A_{i}

が書かれています。

あなたは次の行動を駒がマス

1

かマス

N

に到達するまで繰り返します。

駒がいるマスを

j

とする。空箱の中に

A_{j - 1}

個の赤いボールと

A_{j + 1}

個の青いボールを入れ、ボールをよくかき混ぜた後に無作為に

1

つ取り出す。もし赤のボールが取り出されたなら駒をマス

j - 1

に、そうでないなら駒をマス

j + 1

に動かす。

最終的に駒がマス

N

にある確率を求めてください。ただし、この確率は有理数になることが証明できます。

(21:40追記) 使われる箱は各行動ごとに空にします。

制約

1 \leq K \leq N \leq 10^{5}

1 \leq A_{i} \leq 10 (1 \leq i \leq N)

入力は全て整数

入力

 $N K$ 
 $A_{1} A_{2} \dots A_{N}$

出力

求める確率は互いに素な整数 $p, q$ $(0 \leq p, 0 < q)$ を使って $\frac{p}{q}$ と表すことができます(この $p, q$ は一意に定まります)。この $p$ と $q$ を / で区切って出力してください。

ただし、確率が

0

の時は 0 とのみ出力してください。

サンプル

サンプル1

入力

3 2
1 1 2

出力

2/3

$\frac{1}{3}$ の確率でマス $1$ に行き、 $\frac{2}{3}$ の確率でマス $3$ に行きます。

どちらに行ってもマス

1

かマス

N = 3

に到達するため、答えは

\frac{2}{3}

です。

サンプル2

入力

5 1
1 2 3 4 5

出力

既にマス $1$ に到達しています。

サンプル3

入力

7 3
1 1 2 2 1 2 2

出力

1/2

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