CBOJ 2022 Welcome Contest Problem 2 - First Day of School

Points: 5
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

It's the first day of school at Bone Colly Secondary School!

Harold arrives to class late and finds that some of the seats in the classroom have already been taken. Being the socially awkward person he is, Harold looks for the loneliest seat in the classroom. Can you help him find this seat?

The loneliest seat is defined as the seat in the middle of the longest contiguous segment of unoccupied seats in the classroom. If there are multiple seats with this property, Harold will opt for the seat closest to the classroom exit (the left-most seat holding this property).

Input Specification

The first line will contain an integer $$N$$ $$(3 \le N \le 10^4)$$.

The second line will contain a single string, $$S$$, of length $$N$$. $$S$$, representing the classroom, will consist purely of the digits $$0$$ and $$1$$, denoting whether the seat is empty or occupied, respectively. $$S$$ is guaranteed to start with a $$1$$ and end with a $$1$$, and it will contain at least one $$0$$.

Note: The characters in $$S$$ are generated uniformly (and independently) at random. In particular, each character has a $$50\%$$ chance of being a $$0$$ and a $$50\%$$ chance of being a $$1$$ (except for the first and last characters which are guaranteed to both be $$1$$s).

Output Specification

A single integer representing the $$0$$-based index of the loneliest seat in the classroom.

Sample Input 1

6
100001

Sample Output 1

2

Sample Input 2

5
10001

Sample Output 2

2

Sample Input 3

29
10000000101001000000011100101

Sample Output 3

4

Sample Explanation 3

Seats at index $$4$$ and $$17$$ are both the farthest from any occupied seats, but Harold will opt for seat $$4$$ because $$4 < 17$$.

Sample Input 4

30
100000001010010000000011100101

Sample Output 4

17