## 001: special password lock

Total time limit:

1000ms

Memory limit:

1024kB

describe

There is a special binary password lock, which is composed of N connected buttons (n < 30). The buttons have two states of concave / convex. Pressing the button by hand will change its state.

However, the headache is that when you press a button, the two adjacent buttons will reverse. Of course, if you press the leftmost or rightmost button, it will only affect the button next to it.

The current password lock state is known, and the problem to be solved is how many times you need to press the button to change the password lock to the desired target state.

input

Two lines, giving two equal length strings composed of 0 and 1, representing the current / target password lock state, where 0 represents concave and 1 represents convex.

output

Press the button at least times. If the transformation cannot be realized, the output is impossible.

sample input

011 000

sample output

1

Just press the first one on the left to enumerate by category, compare the times of the two schemes, and take the smaller output. Here, an integer addition operation is used to save the binary number. The following code is highly integrated. It's very brief. Actually, it can be written separately and more clearly

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int oriLock; int lock; int destLock; inline void SetBit(int & n, int i, int v) { if (v) n |= (1 << i); // Set the i-th bit to 1 N? I + 1 or operation else n &= ~(1 << i); // Set the i-th bit to 0 N? I * 0 and operation } inline void FlipBit(int & n, int i) { n ^= (1 << i); // Invert bit i } inline int GetBit(int n, int i) { return (n >> i) & 1; // Use and 1 shift to extract the i-th digit } int main() { char line[40]; //oriLock is the original result, destLock is the target result, and an integer is used to represent the binary number destLock = lock = oriLock = 0; cin >> line; int N = strlen(line); for (int i = 0; i < N; ++i) SetBit(oriLock, i, line[i] - '0'); cin >> line; for (int i = 0; line[i]; ++i) SetBit(destLock, i, line[i] - '0'); int minTimes = 1 << 30; // Press first position press and first position do not press to enumerate for (int p = 0; p < 2; ++p) { lock = oriLock; int times = 0; int curButton = p; for (int i = 0; i < N; ++i) { if (curButton) { ++times; // Here's an integrated approach // Left and right boundaries are considered if (i > 0) FlipBit(lock, i - 1); // Flip this position FlipBit(lock, i); if (i < N - 1) FlipBit(lock, i + 1); } // Flip as long as the current bits are different if (GetBit(lock, i) != GetBit(destLock, i)) curButton = 1; else curButton = 0; } // Judge whether it is the same after turning all if (lock == destLock) minTimes = min(minTimes, times); } if (minTimes == 1 << 30) cout << "impossible" << endl; else cout << minTimes << endl; return 0; }