Farmer John has N cows in a line (1≤N≤3⋅105). Unfortunately, there is a sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads the sickness to the cows on their left and right (if they exist). Once a cow is infected, she stays infected.
After some amount of nights, Farmer John realizes that the issue has gotten out of control, so he tests his cows to determine who has the sickness. Find the minimum number of cows that could have started with the sickness.
INPUT FORMAT (pipe stdin):
The first line contains N, the number of cows that Farmer John has.
The next line contains an N character bitstring of only 1s and 0s where a 1 represents an infected cow and a 0 represents an uninfected cow after some number of nights.
OUTPUT FORMAT (pipe stdout):
Output a single integer: the minimum number of cows that could have started with the sickness.
SAMPLE INPUT:
5
11111
SAMPLE OUTPUT:
1
Suppose the middle cow was the only cow to start off infected. Then the cows would be infected in the following order:
After two or more nights, the final state of the cows would look like the input. There are many other initial states and number of nights that could have produced the input state, such as:
All of these initial states contain at least one infected cow.
SAMPLE INPUT:
6
011101
SAMPLE OUTPUT:
4
The only initial state and number of nights that could have led to this final state is if no nights have passed and each of the four infected cows in the input started off with the sickness.
SCORING:
Inputs 3-7: N≤1000
Inputs 8-12: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
