In the city where you live, Kickstartland, there is one particularly long street with NN houses on it. This street has length NN, and the NN houses are evenly placed along it, that is, the first house is at position 11, the second house is at position 22, and so on. The distance between any pair of houses ii and jj is |i−j||i−j|, where |x||x| denotes the absolute value of xx.

Trash Bins solution kickstart

Problem

In the city where you live, Kickstartland, there is one particularly long street with NN houses on it. This street has length NN, and the NN houses are evenly placed along it, that is, the first house is at position 11, the second house is at position 22, and so on. The distance between any pair of houses ii and jj is |ij||i−j|, where |x||x| denotes the absolute value of xx.

Some of these houses have trash bins in front of them. That means that the owners of such houses do not have to walk when they want to take their trash out. However, for the owners of houses that do not have trash bins in front of them, they have to walk towards some house that has a trash bin in front of it, either to the left or to the right of their own house.

To save time, every house owner always takes their trash out to the trash bin that is closest to their houses. If there are two trash bins that are both the closest to a house, then the house owner can walk to any of them.

Given the number of houses NN, and the description of which of these houses have trash bins in front of them, find out what is the sum of the distances that each house owner has to walk to take their trashes out. You can assume that at least one house has a trash bin in front of it.

Trash Bins solution kickstart

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case consists of two lines.

The first line of each test case contains an integer NN, denoting the number of houses on the street.

The second line of each test case contains a string SS of length NN, representing which houses have trash bins in front of them. If the ii-th character in string SS is equal to 11, then it means that the ii-th house has a trash bin in front of it. Otherwise, if it is equal to 00, then it means that the ii-th house does not have a trash bin in front of it.

Trash Bins solution kickstart

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the sum of the distances that each house owner has to walk to take their trashes out.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
The length of SS is equal to NN.
Each character of SS is either 00 or 11.
There is at least one character 11 in SS.

Trash Bins solution kickstart

1N1001≤N≤100.

Test Set 2

1N5×1051≤N≤5×105.

Trash Bins solution kickstart

Sample Input
content_copy
2
3
111
6
100100
Sample Output
content_copy
Case #1: 0
Case #2: 5

For the first test case, every house has a trash bin in front of it, and therefore none of the house owners will have to walk to take their trashes out.

For the second test case, the first and the fourth house owners have trash bins in front of their houses, and therefore will not have to walk. The second house owner will walk towards the first house, and the distance will be equal to 11. The third, fifth, and sixth house owners will walk towards the fourth house, and the distances will be

Leave a Comment