新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
鎖
問題 
バイトランドはずっと民主主義国であったわけではない。その歴史には黒く塗られたページが存在する。ある日、バイトランドの権力者ジャンタの総司令官バイテルは、長い間続いた戦いを終わらせ、囚われた活動家たちを解放することにした。しかし、彼は活動家のリーダーであるバイトサーを解放できる力はなかった。バイテルは、バイトサーをバイトランドの鎖で壁に繋ぐことにした。バイトランド鎖は、壁に固定された棒と繋がった輪からなる。輪が棒に固定されていないにもかかわらず、これを外すのは困難である。
「総統、なぜ私は壁に囚われ、自由を満喫することが許されないのですか！」と、バイトサーは泣いた。
「バイトサー、あなたは完全に鎖で繋がれているわけではない。あなたなら自分で輪を棒から外すことができると信じている。」バイテルは裏切るように言った。
「ただ、時計がサイバー時間を示す前に実行し、音をたててはならない。でなければ私は市民サイバー警察を呼ぶことになる。」
バイトサーを助けよう！鎖の輪を整数1,2,...,nで番号づけする。以下のルールに従って、これらの輪を外したりつけたりできる:
- 1回の操作で、ちょうど1つの輪をつけたり外したりできる。
- 輪1はいつでもつけたり外したりできる。
- 1<=k<nについて、k-1以下の輪が全て外されていて、kの輪がつけられていたら、k+1の輪をつけたり外したりできる。
- バイトランド鎖の状態を標準入力から入力する。
- そして、バイトランド鎖の全ての輪を棒から外すのにかかる手数を計算する。
- 最後にそれを標準出力に出力せよ。
入力
入力の最初の行には、整数n(1 <= n <= 1000)が書かれている。次の行には、n個の整数o1,o2,...on(どの数字も0または1のどちらかである)が空白を区切りとして書かれている。もしoi=1なら、i番目の輪は棒につけられていて、oi=0なら、i番目の輪は棒から外されている。
出力
出力は、全ての輪を外すのにかかる最小手数を記した1つの整数を含む1行からなる。
入力例
4 1 0 1 0
出力例
6
出典
POI 2001
