lamps.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <string>
using namespace std;
bool use[5]={0};
int N,C;
int off[101],offnum=0;
int on[101],onnum=0;
bool hash[101];
int answernum=0;
string answers[20];
void check()
{
	int tC=0;
	for(int a=1;a<=4;a++)
		if(use[a])
			tC++;
	if(tC>C)
		return;
	for(int a=1;a<=N;a++)
		hash[a]=true;
	if(use[1])
		for(int a=1;a<=N;a++)
			hash[a]=!hash[a];
	if(use[2])
		for(int a=1;a<=N;a+=2)
			hash[a]=!hash[a];
	if(use[3])
		for(int a=2;a<=N;a+=2)
			hash[a]=!hash[a];
	if(use[4])
		for(int a=1;a<=N;a+=3)
			hash[a]=!hash[a];
	for(int a=1;a<=offnum;a++)
		if(hash[off[a]]) return;
	for(int a=1;a<=onnum;a++)
		if(!hash[on[a]]) return;
	answers[++answernum]="";
	for(int a=1;a<=N;a++)
		if(hash[a])
			answers[answernum]+='1';
		else
			answers[answernum]+='0';
}

void searchit(int n)
{
	if(n==5)
		check();
	else
	{
		if(n<=4)
		{
			use[n]=true;
			searchit(n+1);
			use[n]=false;
			searchit(n+1);
		}
	}
}

int main()
{
	freopen("lamps.in","r",stdin);
	freopen("lamps.out","w",stdout);
	scanf("%d%d",&N,&C);
	int t;
	while(true)
	{
		scanf("%d",&t);
		if(t==-1) break;
		else on[++onnum]=t;
	}
	while(true)
	{
		scanf("%d",&t);
		if(t==-1) break;
		else off[++offnum]=t;
	}
	searchit(1);
	if(answernum==0)
		printf("IMPOSSIBLE\n");
	else
	{
		for(int a=2;a<=answernum;a++)
			for(int b=a-1;b>=1;b--)
				if(answers[b]==answers[a])
				{
					answers[a]=answers[answernum];
					answernum--;
					a--;
					break;
				}
		string st;
		for(int a=1;a<answernum;a++)
			for(int b=a+1;b<=answernum;b++)
				if(answers[b]<answers[a])
				{st=answers[b];answers[b]=answers[a];answers[a]=st;}
		for(int a=1;a<=answernum;a++)
			printf("%s\n",answers[a].c_str());
	}
	return 0;
}