Score : 700 points
N cells are arranged in a row.
Some of them may contain tokens.
You are given a string s that consists of 0
s and 1
s.
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?
0
or 1
.Input is given from Standard Input in the following format:
N s
Print the answer.
7 1010101
2
For example, he can perform two operations in the following way:
1010010
.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.
50 10101000010011011110001001111110000101010111100110
10