/*
* 1.cpp
*
* Created on: 2017年8月30日
* Author: Administrator
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string result,s,lock;
int temp = 0 ,answer = 1e9, n;
void press(int i){
s[i-1] = s[i-1] == '1'?'0':'1';
s[i] = s[i] == '1'?'0':'1';
if(i+1<n)
s[i+1] = s[i+1] == '1'?'0':'1';
}
int main(){
cin>>lock>>result;
s = lock;
n = lock.size();
//第一种情况，当前字符不相同时，从下一个字符开始按按钮
for( int i = 1; i<n; i++){
if(s[i-1] != result[i-1]){
press(i);
temp ++ ;
}
}
//可能的结果一:
if(s[n-1] == result[n-1]){
answer = temp ;
}
// 第二种情况：如果前两个按钮不匹配，按第一个按钮，其他按钮不匹配还是按后一个按钮
s = lock;
temp = 1;
if( s[0] != result[0] || s[1] != result[1]){
s[0] = s[0] == '1'?'0':'1';
s[1] = s[1] == '1'?'0':'1';
for(int i = 1; i< n; i++){
if(s[i-1] != result[i-1]){
press(i);
temp ++;
}
}
}
//可能的结果二:
if(s[n-1] == result[n-1]){
answer = min(answer,temp);
}
if(answer == 1e9){
cout<< "impossible";
}
else{
cout<< answer;
}
return 0 ;
}
思路：
看到输入输出首先想到的是枚举所有按钮的状态，但是n的范围为30，所以会有2的30次方多种，所以肯定不能枚举出所有状态，于是用到了一个贪心策略，从左往右，如果按钮不匹配就按下一个按钮，始终让左面的按钮是匹配的，如果遍历到最后一个按钮不匹配则"impossible"，否则输出最少的按钮次数。但是容易忽略一个特殊情况，即前两个按钮，当前两个按钮不匹配时既可以按第一个按钮也可以按第二个按钮，所以应当考虑这两种情况最后哪中情况按的次数少。
