卢俊达

题目大意：

给出一排灯，4个按钮，每个按钮可以使特定位置的灯改变状态。规定操作数c和目标状态，输出c次操作后所有符合目标状态的状态。

思路：

利用深搜按操作次数枚举4^c个状态。

代码：

/*
ID: lujunda1
LANG: C++
PROG: lamps
*/
#include<iostream>
#include<stdio.h>
#include<map>
#include<cstring>
using namespace std;
int n,c,total;
bool on[102],off[102];
//on[]、off[]用于记录目标状态。 
map<string,bool> mark;
//对状态进行标记，避免重复搜索。 
struct point 
//对用结构体对状态进行封装，便于利用qsort排序。
{
	char arry[102];
}res[16]; 
int cmp(const void* m,const void* n)
//qsort的排序函数。 
{
	return strcmp((*(point*)m).arry+1,(*(point*)n).arry+1);
	//注意下标是从1开始的，而不是0。 
}
void input()
//输入 
{
	scanf("%d%d",&n,&c);
	if(c>4)
		c=c%2?3:4;
		//注意对C的处理，当c>4时，必然会出现同一按钮按多次的情况。 
	for(int i=0;i<102;i++)
		on[i]=off[i]=false;
	int t;
	while(~scanf("%d",&t)&&t!=-1)
		on[t]=true;
	while(~scanf("%d",&t)&&t!=-1)
		off[t]=true;
}
void output()
//输出 
{
	if(!total)
	{
		printf("IMPOSSIBLE\n");
		return;
	}
	qsort(res,total,sizeof(res[0]),cmp);
	for(int i=0;i<total;i++)
		printf("%s\n",res[i].arry+1);
}
point op(int t,point temp)
//operation操作函数。
//参数t表示按钮编号。
//temp表示按钮作用的对象状态。 
{
	if(t==1)
		for(int i=1;i<=n;i++)
			temp.arry[i]=temp.arry[i]-'0'?'0':'1';
	else if(t==2)
		for(int i=1;i<=n;i+=2)
			temp.arry[i]=temp.arry[i]-'0'?'0':'1';
	else if(t==3)
		for(int i=2;i<=n;i+=2)
			temp.arry[i]=temp.arry[i]-'0'?'0':'1';
	else
		for(int i=0;3*i+1<=n;i++)
			temp.arry[3*i+1]=temp.arry[3*i+1]-'0'?'0':'1';
	return temp;
}
bool check(point temp)
//检查temp是否与目标状态相符。 
{
	for(int i=1;i<=n;i++)
	{
		if(on[i]&&temp.arry[i]=='0')
			return false;
		if(off[i]&&temp.arry[i]=='1')
			return false;
	}
	string result=temp.arry;
	if(mark[result])
	//检查temp是否与其他已确定的状态相重复。 
		return false;
	mark[result]=true;
	return true;
}
void dfs(point temp,int sum)
//利用深搜枚举4^c种状态。 
{
	if(sum==c)
	{
		if(check(temp))
			res[total++]=temp;
		return;
	}
	for(int i=1;i<5;i++)
		dfs(op(i,temp),sum+1);
}
int main()
{
	freopen("lamps.in","r",stdin);
	freopen("lamps.out","w",stdout);
	input();
	total=0;
	//符合目标状态的状态的总数。初始化为0。 
	point temp;
	for(int i=1;i<=n;i++)
		temp.arry[i]='1';
	temp.arry[n+1]='\0';
	dfs(temp,0);
	output();
}