D - 101 to 010 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

N 個のセルが一列に並んでいます。 何個かのセルはトークンを含んでいるかもしれません。 あなたは、 0 と 1 からなる文字列 s が与えられます。 s の i 文字目が 1 のとき、(左から) i 番目のセルはトークンを一個含んでいます。 そうでないとき、トークンを含んでいません。

すぬけ君は、以下の操作をできる限り行いたいです。 各操作では、三個の連続するセルを選びます。 セルを左から X, Y, Z とします。 操作を行うためには、 X と Z の両方がトークンを含み、 Y はトークンを含んでいてはなりません。 次に、すぬけ君はこれらの二個のトークンを取り除き、新しいトークンを Y に一個置きます。

最適な操作の方法をしたとき、すぬけ君は何回操作を行えますか？

制約

  • 1 \leq N \leq 500,000
  • |s| = N
  • s の各文字は 0 または 1 である。

入力

入力は以下の形式で標準入力から与えられる。

N
s

出力

答えを出力せよ。

入力例 1

7
1010101

出力例 1

2

例えば、以下の方法で操作を二回行うことができます:

  • 最後の三個のセルに対し操作を行う。 トークンを表す文字列は 1010010 となる。
  • 最初の三個のセルに対し操作を行う。 トークンを表す文字列は 0100010 となる。

操作の順番が重要であることに注意してください。 たとえば、最初に中央の三個のセルを選ぶと、それ以上操作を行えなくなります。

入力例 2

50
10101000010011011110001001111110000101010111100110

出力例 2

10

Score : 700 points

Problem Statement

N cells are arranged in a row. Some of them may contain tokens. You are given a string s that consists of 0s and 1s. If the i-th character of s is 1, the i-th cell (from left) contains a token. Otherwise, it doesn't contain a token.

Snuke wants to perform the following operation as many times as possible. In each operation, he chooses three consecutive cells. Let's call the cells X, Y, Z from left to right. In order for the operation to be valid, both X and Z must contain tokens and Y must not contain a token. Then, he removes these two tokens and puts a new token on Y.

How many operations can he perform if he performs operations in the optimal way?

Constraints

  • 1 \leq N \leq 500,000
  • |s| = N
  • Each character in s is either 0 or 1.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the answer.

Sample Input 1

7
1010101

Sample Output 1

2

For example, he can perform two operations in the following way:

  • Perform an operation on the last three cells. Now the string that represents tokens becomes 1010010.
  • Perform an operation on the first three cells. Now the string that represents tokens becomes 0100010.

Note that the choice of operations matters. For example, if he chooses three cells in the middle first, he can perform no more operations.

Sample Input 2

50
10101000010011011110001001111110000101010111100110

Sample Output 2

10