#P1468. [USACO2.2] 派对灯 Party Lamps
[USACO2.2] 派对灯 Party Lamps
题目描述
在 IOI98 的节日宴会上,我们有 盏彩色灯,他们分别从 被标上号码。这些灯都连接到四个按钮:
按钮 :当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。
按钮 :当按下此按钮,将改变所有奇数号的灯。
按钮 :当按下此按钮,将改变所有偶数号的灯。
按钮 :当按下此按钮,将改变所有序号是 的灯。例如:
一个计数器 记录按钮被按下的次数。当宴会开始,所有的灯都亮着,此时计数器 为 。
你将得到计数器 上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态,并且没有重复。
输入格式
第一行一个正整数 ;第二行一个整数 ,表示最后计数器的数值。
第三行若干个整数,表示最后亮着的灯,以 -1
结束。
第四行若干个整数,表示最后关着的灯,以 -1
结束。
保证不会有灯会在输入中出现两次。
输出格式
每一行是所有灯可能的最后状态(没有重复)。
每一行有 个字符,第 个字符表示 号灯。 表示关闭, 表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行 IMPOSSIBLE
。
10
1
-1
7 -1
0000000000
0101010101
0110110110
提示
【数据范围】
对于 的数据,,。
【样例解释】
在这个样例中,有三种可能的状态:
-
所有灯都关着
-
号灯关着, 亮着。
-
号灯关着, 亮着。
翻译来自NOCOW
USACO 2.2