A new puzzle has begun trending recently: LXghts Out!
The puzzle consists of a row of 1
and 0
, respectively. In one move, you can choose any light and set its on/off state to the bitwise xor of its neighbours (adjacent lights). In other words,
- You can only turn a light on if exactly
of its neighbours is on. or - You can only turn a light off if
or of its neighbours are on. or
Note that light
The goal of the game is to turn off all of the lights with the minimum number of moves.
All the cool kids in town are racing each other to see who can complete the puzzle the fastest, but you, the programmer, have a few tricks up your sleeve. Before you begin racing, you will use your insane hacking skills to flip the on/off state of at most
Can you find the minimum number of moves to solve the puzzle after flipping at most -1
.
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
Input Specification
The first line of input contains two integers,
The next line contains 1
represents on and 0
represents off.
Output Specification
Output one line containing one integer, the minimum number of moves to solve the puzzle after flipping at most
If the puzzle is always impossible, output -1
instead.
Sample Input 1
6 1
110110
Sample Output 1
5
Explanation for Sample 1
One possible solution is to flip the first light, to get 010110
.
Then, you can solve the puzzle in
010110
000110
- turn off light 2 (0 neighbours on)
000111
- turn on light 6 (1 neighbour on)
000101
- turn off light 5 (2 neighbours on)
000001
- turn off light 4 (0 neighbours on)
000000
- turn off light 6 (0 neighbours on)
It can be shown that
Sample Input 2
4 2
0000
Sample Output 2
0
Explanation for Sample 2
In this example, it is optimal to not flip any lights beforehand, since the puzzle is already solved! Thus, the minimum number of moves afterwards is
Sample Input 3
2 0
11
Sample Output 3
-1
Explanation for Sample 3
You cannot flip any lights beforehand, since
Comments