A supply channel is marked by n buoys in a straight line, numbered 0 through n - 1 from one end to the other. Some buoys currently hold a shipping crate and some do not. In a single transfer, a crate sitting on a buoy can be moved onto an immediately neighboring buoy (index -1 or +1). For every buoy i, the harbor master wants to know the minimum total number of transfers needed to gather all of the channel's crates onto buoy i: a crate that starts k buoys away needs exactly k transfers, crates already on buoy i need zero, and moving different crates never blocks or interferes with each other.
The first line contains a single integer n. The second line contains a string of exactly n characters, each either 0 (no crate) or 1 (one crate), where the character at position i (0-indexed) describes buoy i.
Print n space-separated integers on one line: the i-th integer is the minimum total number of transfers needed to gather every crate onto buoy i.
1 <= n <= 2000.n and consists only of the characters 0 and 1.Example 1
Input
4 1100
Expected
1 1 3 5
Explanation
Crates sit on buoys 0 and 1. Gathering both onto buoy 0 costs |0-0|+|1-0|=1; onto buoy 1 costs |0-1|+|1-1|=1; onto buoy 2 costs |0-2|+|1-2|=3; onto buoy 3 costs |0-3|+|1-3|=5. So the answer is 1 1 3 5.
Example 2
Input
5 10101
Expected
6 5 4 5 6
Explanation
Crates sit on buoys 0, 2, and 4. For buoy i the cost is |i-0|+|i-2|+|i-4|. Buoy 0: 0+2+4=6. Buoy 1: 1+1+3=5. Buoy 2: 2+0+2=4. Buoy 3: 3+1+1=5. Buoy 4: 4+2+0=6. So the answer is 6 5 4 5 6.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →