CBOJ 2022 Welcome Contest Problem 2 - First Day of School

Submit solution

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

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


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3


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


Sample Output 4



There are no comments at the moment.