Mock CCC '20 Contest 1 J4 - A Binary Problem

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

koosaga lives on a street with N houses, all equally spaced apart. Each house either has the lights on or off. koosaga rates a house with a score equal to the minimum distance, in house units, that he must travel to be at a house that has its lights on.

koosaga wants to compute the sum of the ratings of all the houses on his street.

Constraints

1 \le N \le 10^6

In tests worth 5 marks, N \le 10^3.

At least one house will always have its lights on.

Input Specification

The first line contains a single positive integer, N.

The next line contains a binary string. If the ith character of the string is 1, then the ith house has its lights on. Otherwise, the ith character of the string is 0 and that house has its lights off.

Output Specification

Output the sum of all the ratings.

Sample Input 1

3
111

Sample Output 1

0

Explanation for Sample 1

Every house is illuminated, so every house has a rating of 0.

Sample Input 2

4
1001

Sample Output 2

2

Explanation for Sample 2

The first and last house have ratings of 0, and the second and third house each have a rating of 1.


Comments

There are no comments at the moment.