/**//*
ID: lorelei3
TASK: lamps
LANG: C++
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
const int C = 4;
const int MAXN = 6;
const int MASK = (1<<MAXN)-1;
int loc[1<<MAXN];
int n,c,t;
int open_mask, tot_mask;
int op[4] = 
{ MASK,
MASK & 0xAA,
MASK & 0x55,
MASK & ( (1<<(MAXN-1)) | (1<<(MAXN-4)) )
};
FILE *fin, *fout;
void wirte(int lights){
int i;
char s[105];
for(i=0; i<n; ++i)
s[i] = ( lights & (1<<(MAXN-1-(i%MAXN))) ) ? '1': '0';
s[i]='\0';
fprintf(fout, "%s\n", s);
}
void dfs(int lights, int i, int n){
if(n==c){
if( (lights&tot_mask)==open_mask){
loc[lights]=1;
return;
}
}else
for( ; i<4; ++i)
dfs( lights^op[i], i+1, n+1);
}
int main(){
int i;
fin = fopen("lamps.in", "r");
fout = fopen("lamps.out", "w");
assert(fin!=NULL && fout!=NULL);
fscanf(fin, "%d %d", &n, &c);
for(;;){
fscanf(fin, "%d", &t);
if(t==-1) break;
t = MAXN-1-(t-1)%MAXN;
open_mask |= (1<<t);
tot_mask |= (1<<t);
}
for(;;){
fscanf(fin, "%d", &t);
if(t==-1) break;
t = MAXN-1-(t-1)%MAXN;
tot_mask |= (1<<t);
}
if(c>4){
if(c%2==0)
c=4;
else
c=3;
}
for(i=0; i<=c; i+=2)
dfs(MASK, 0, i);
bool flag=false;
for(i=0; i< (1<<MAXN); ++i)
if(loc[i]){
flag = true;
wirte(i);
}
if(!flag)
fprintf(fout, "IMPOSSIBLE\n");
return 0;
}posted on 2010-11-21 00:49
小阮 阅读(135)
评论(0) 编辑 收藏 引用 所属分类:
USACO