問題一覧 > 通常問題

No.1501 Random Walk

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : 👑 qand / テスター : nok0
お気に入りにしたユーザー ProblemId : 6270 / 自分の提出
問題文最終更新日: 2021-05-08 01:20:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 294 (順位表) の他の問題:

Problem Statement

There are $N$ cells numbered from $1$ to $N$ and $1$ piece. Initially, the piece is placed on cell $K$.

An integer is written on each cell, and $A_i$ is written on cell $i$.

You repeat the following action until the piece reaches cell $1$ or cell $N$.

  • Let $j$ be the cell the piece is on. Put $A_{j-1}$ red balls and $A_{j+1}$ blue balls into an empty box, mix the balls well, and then take out $1$ ball at random. If a red ball is taken out, move the piece to cell $j-1$; otherwise, move the piece to cell $j+1$.

    • Find the probability that the piece is finally on cell $N$. It can be proved that this probability is a rational number.

    (Added at 21:40) The box used is emptied for each action.

    Constraints

  • $1\le K\le N\le 10^5$
  • $1\le A_i\le 10\ (1\le i\le N)$
  • All inputs are integers

    • Input

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

    Output

    The required probability can be expressed as $\displaystyle\frac pq$ using coprime integers $p,q$ $(0\le p,0< q)$ (these $p,q$ are uniquely determined). Output $p$ and $q$ separated by /.

    However, if the probability is $0$, output only 0.

    Sample

    Sample 1
    Input
    3 2
1 1 2
    Output
    2/3

    The piece goes to cell $1$ with probability $\displaystyle\frac13$ and to cell $3$ with probability $\displaystyle\frac23$.

    Either way, it reaches cell $1$ or cell $N=3$, so the answer is $\displaystyle\frac23$.

    Sample 2
    Input
    5 1
1 2 3 4 5
    Output
    0

    The piece has already reached cell $1$.

    Sample 3
    Input
    7 3
1 1 2 2 1 2 2
    Output
    1/2

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