問題一覧 > 通常問題

No.1765 While Shining

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 118
作問者 : first_vilfirst_vil / テスター : 👑 koboshikoboshi 👑 ygussanyygussany
0 ProblemId : 7203 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-26 14:45:58

問題文

$N$ 個のマスが横一列に並んだマス目があります。左から $i$ 個目のマスをマス $i$ と呼びます。初期状態ではマス $i$ は $A_i=1$ ならば輝いていて、$A_i=0$ ならば輝いていません。

あなたはこれからいずれかのマスにロボットを置きます。置かれたロボットは以下の一連の動作を繰り返し行います。

  1. 今いるマスがマス $N$ であるか輝いていない場合は動作を停止する。
  2. $1$ つ右のマスに移動した後、全てのマスの「輝いている」「輝いていない」の状態を反転する。

それぞれのマスについてロボットをそのマスに置いた場合にロボットが移動する回数を求め、それらの総和を答えてください。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
  • 入力はすべて整数
  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 1$

出力

ロボットが移動する回数の総和を出力し、最後に改行してください。

サンプル

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

マス $1$ やマス $2$ にロボットを置くと $1$ 回移動した直後に今いるマスが輝いていない状態に変化するため、$1$ つ右のマスで動作が停止します。

マス $3$ にロボットを置くと毎回の移動直後に今いるマスが輝いている状態に変化するため、マス $5$ まで到達します。

サンプル2
入力
8
0 1 0 1 1 0 0 1
出力
6

サンプル3
入力
15
0 0 0 1 1 0 0 0 1 0 1 0 0 1 1
出力
10

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