题目 1959:
蓝桥杯算法提高VIP-Light Bulbs
时间限制: 2s
内存限制: 192MB 提交: 10 解决: 0
题目描述
好莱坞最新的剧院“the Atheneum of Culture and Movies”拥有一个由计算机控制的成千上万个灯泡组成的巨型荧幕。每行灯泡都用由电脑操作的一系列开关控制。不幸的是，电工接错了开关的型号，并且今天晚上就是ACM的开幕式。你需要写个程序让这些开关正确的运作。
荧幕的一排有n个灯泡，它们被n个开关控制。灯泡和开关都从左至右依次编号为1到n。每个灯泡要么是开的，要么是关的。每组输入数据含有一排灯泡的起始状态和目标状态。
最初的计划是让一个开关控制一个灯泡。但是电工的失误导致了每个开关控制2或3个灯泡，如图1所示。最左边的开关（i=1）控制最左边的两个灯泡（1和2）；最右边的灯泡（i=n）控制最右边的两个灯泡（n-1和n）。剩下的开关（1<i<n）控制3个灯泡i-1，i和i+1。（特别的，如果只有1个灯泡，那么就只有1个开关控制那唯一的灯泡。）也就是说，如果灯泡1是开的，灯泡2是关的，转换开关1则会导致灯泡1关上，灯泡2打开。最少的代价是指将这一排灯泡从初始状态转换到最终状态所需要转换的最少的开关数。
你可以将一排开关的状态表示为二进制数，0表示关，1表示开。举例来说，01100表示一排5个灯泡，其中第二个和第三个是开的。如果要把这个状态转化到10000，可以转换开关1、4、5，或者转换开关2。
你需要写个程序来决定最少转换哪些开关使得这排灯泡从初始状态变为目标状态。有些初始状态和目标状态是无解的。为了压缩数据，我们用10进制来输入。也就是说，01100和10000将用12和16来表示。
荧幕的一排有n个灯泡，它们被n个开关控制。灯泡和开关都从左至右依次编号为1到n。每个灯泡要么是开的，要么是关的。每组输入数据含有一排灯泡的起始状态和目标状态。
最初的计划是让一个开关控制一个灯泡。但是电工的失误导致了每个开关控制2或3个灯泡，如图1所示。最左边的开关（i=1）控制最左边的两个灯泡（1和2）；最右边的灯泡（i=n）控制最右边的两个灯泡（n-1和n）。剩下的开关（1<i<n）控制3个灯泡i-1，i和i+1。（特别的，如果只有1个灯泡，那么就只有1个开关控制那唯一的灯泡。）也就是说，如果灯泡1是开的，灯泡2是关的，转换开关1则会导致灯泡1关上，灯泡2打开。最少的代价是指将这一排灯泡从初始状态转换到最终状态所需要转换的最少的开关数。
你可以将一排开关的状态表示为二进制数，0表示关，1表示开。举例来说，01100表示一排5个灯泡，其中第二个和第三个是开的。如果要把这个状态转化到10000，可以转换开关1、4、5，或者转换开关2。
你需要写个程序来决定最少转换哪些开关使得这排灯泡从初始状态变为目标状态。有些初始状态和目标状态是无解的。为了压缩数据，我们用10进制来输入。也就是说，01100和10000将用12和16来表示。
输入格式
输入数据有多个case。每个case一行，2个非负整数，其中至少有一个是整数，并且不超过100个数字。第一个数字表示开始状态，第二个数字表示目标状态。这些数字化为2进制后表示一行灯泡的状态，1是开，0是关。
为了避免二进制数中出现前导0的问题，数据保证第一个灯泡要么在起始状态是亮的，要么是在目标状态是亮的（或者都是亮的）。输入保证没有多余的空格，输入的10进制数中没有前导0，两个数由一个空格隔开。
为了避免二进制数中出现前导0的问题，数据保证第一个灯泡要么在起始状态是亮的，要么是在目标状态是亮的（或者都是亮的）。输入保证没有多余的空格，输入的10进制数中没有前导0，两个数由一个空格隔开。
输出格式
对每个case，输出一行。包括case编号和一个十进制数。这个十进制数表示在最小代价下，需要转换的开关的状态。也就是说如果把这个数转为2进制后，最右边的位（最低位）代表第n个开关的状态，1表示开关转换过，0表示没有。如果无解，输出“impossible”。如果有多组解，输出转成十进制后最小的那一个。
在每个case间输出一个空行，用输出样例显示的格式输出。
在每个case间输出一个空行，用输出样例显示的格式输出。
样例输入
12 16 1 1 3 0 30 5 7038312 7427958190 4253404109 657546225 0 0
样例输出
Case Number 1: 8 Case Number 2: 0 Case Number 3: 1 Case Number 4: 10 Case Number 5: 2805591535 Case Number 6: impossible