問題一覧 > 通常問題

No.1501 酔歩

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 38
作問者 : 遭難者遭難者 / テスター : nok0nok0
9 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\le K\le N\le 10^5$
  • $1\le A_i\le 10\ (1\le i\le N)$
  • 入力は全て整数
  • 入力

    $N\ K$
    $A_1\ A_2\ \ldots\ A_N$
    

    出力

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

    ただし、確率が $0$ の時は 0 とのみ出力してください。

    サンプル

    サンプル1
    入力
    3 2
    1 1 2
    出力
    2/3

    $\displaystyle\frac13$ の確率でマス $1$ に行き、 $\displaystyle\frac23$ の確率でマス $3$ に行きます。

    どちらに行ってもマス $1$ かマス $N=3$ に到達するため、答えは $\displaystyle\frac23$ です。

    サンプル2
    入力
    5 1
    1 2 3 4 5
    出力
    0

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

    サンプル3
    入力
    7 3
    1 1 2 2 1 2 2
    出力
    1/2

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