Problem F
Paired Furnaces
Just outside the entrance to your mine shaft you have a row of $n$ furnaces; some of them are on and some are off. Unlike regular furnaces, these furnaces can only be turned on in neighboring pairs. In one move you can either choose two neighboring furnaces which are on and turn both of them off, or choose two neighboring furnaces which are off and turn both of them on.
You want to turn all of them on as quickly as possible. If it is possible to turn all the furnaces on, output the minimum number of moves to do so. Otherwise, output “impossible”.
Input
The first line contains one integer $n$, $1 \leq n \leq 10^6$. The next line contains a binary string $s$ of length $n$, where $s_ i=0$ means the $i$th furnace in the row is off and $s_ i=1$ means the $i$th furnace in the row is on.
Output
The minimum number of moves to turn all of the furnaces on, or “impossible” if it is not possible to do so.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 0 |
impossible |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 0110 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 010101101010 |
21 |
