問題一覧 > 通常問題

No.1840 Random Painting

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : Sumitacchan / テスター : 👑 hitonanode ygussany
お気に入りにしたユーザー ProblemId : 6872 / 自分の提出
問題文最終更新日: 2022-01-16 17:06:09
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 331 (順位表) の他の問題:

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 1 if tile $i$ is painted black, and $s_i$ is 0 if 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 0 and 1.
  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。