No.1840 Random Painting
タグ : / 解いたユーザー数 18
作問者 :
Sumitacchan
/ テスター :
👑
hitonanode
Problem Statement
$N$ tiles numbered $1,2,\dots,N$ are arranged in this order on a circle.
For each integer $i\ (1\le i\le N-1)$, the tile to the right of tile $i$ is tile $i+1$, and the tile to the right of tile $N$ is tile $1$.
Some tiles, including tile $1$, are painted black, and the other tiles are not painted yet.
The color information of the tiles is given as a string $s=s_1s_2\cdots s_N$ of length $N$ consisting of 0, 1, as follows.
- For each integer $i\ (1\le i\le N)$, $s_i$ is
1if tile $i$ is painted black, and $s_i$ is0if it is not painted.
Initially, Yuki is at tile $1$.
Until all the tiles are painted black, Yuki repeats an action consisting of the following sequence of steps.
- Choose either the tile to the right or the tile to the left of the tile Yuki is currently on with equal probability (probability $1/2$ each), and move to it.
- If the destination tile is not painted yet, paint it black.
Find the expected number of actions until all the tiles are painted black.
It can be proved from the constraints that this value is a non-negative integer not greater than $10^{18}$.
Input
$N$ $s$
- $2\le N\le 10^6$
- $N$ is an integer.
- $s$ is a string of length $N$ consisting only of
0and1. - $s_1$ is
1. - $s$ contains at least $1$
0.
Output
Output the expected number of actions until all the tiles are painted black, as an integer.
Sample
Sample 1
Input
2 10
Output
1
In action number $1$, Yuki always moves to tile $2$, and all the tiles become painted black.
Sample 2
Input
3 110
Output
2
It suffices to find the expected number of actions until Yuki moves to tile $3$ for the first time.
Whether Yuki is at tile $1,2$, the probability of moving to tile $3$ is $1/2$, so the expected number of actions is $2$.
Sample 3
Input
10 1000110010
Output
41
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。