#P2159. 为奶牛熄灯(xlite)
为奶牛熄灯(xlite)
【问题描述】
奶牛们喜欢在黑暗的环境里睡觉。当她们每晚回到牛棚准备睡觉时,牛棚里有L(3<=L<=50)盏灯仍然亮着。所有灯的开关按编号升序排成一列,最左边的那个开关控制1号灯(所谓控制,也就是如果1号灯现在亮着,那么按这个开关会使1号灯熄灭,否则这个操作会使1号灯被点亮)。
由于奶牛们的蹄子过于粗大,没法方便地按开关,她们总是用一个特制的干草叉来进行对开关的操作。这个叉子设计了T(1<=T<=7)个叉尖,相邻叉尖的距离正好与相邻开关的距离相等。但是现在有些叉尖被折断了。比如说,T=4的一个干草叉,它的第3根叉尖被折断了,我们就用'1101'来描述它。
如果把这个叉子的最左端对准那一列开关的最左端,按下,那1号、2号和4号灯的状态会被改变(3号灯的状态不变,因为那个叉尖被折断了)。在进行这样的操作的时候,任何一个叉尖都必须有一个对应的开关,也就是说,叉子的边缘不能在那一列开关的范围外,即使边缘处的叉尖已经被折断。
现在,你已经知道了各个灯的状态,以及干草叉现在的情况,请你找出一个操作序列,使得在所有操作完成之后,仍然亮着的灯的数目最少。
【输入格式】
- 第1行: 两个用空格隔开的整数:L 和 T
- 第2行: 一个长度为L的字符串,串中不含空格且元素均为'0'或'1'。第i个元素是'1'则表示第i盏灯亮着,是'0'的话就表示第i盏灯已经被关掉
- 第3行: 一个长度为T的字符串,只含'0'或'1'(同样不含空格)。如果第i个元素是'1',说明干草叉的第i根叉尖仍完好无损,否则说明第i根叉尖已经被折断
输入样例 (xlite.in):
10 4
1111111111
1101
输入说明:
所有的10盏灯都开着。奶牛们使用的干草叉有4个齿,其中第3个齿已经被折断了。
输出格式:
- 第1行: 输出一个正整数K,即为了达到目的一共需要用叉子按多少次开关
- 第2..K+1行: 每行输出一个正整数X(1<=X<=L-T+1),表示干草叉最左边的齿所对的开关的编号。 我们的目标是使亮着的灯尽可能少,如果你用最少的操作次数完成了这个目标,那你可以拿到这个测试点的满分;如果你的输出能达到这个目标但用了更多一些的操作,你可以拿到部分分。所有亮着的灯并不总是能被全部熄灭
输出样例 (xlite.out):
5
3
1
4
7
6
输出说明:
1111111111 开始
1100101111 操作 3(即为把叉子的第一个齿对准第3个开关,按下)
0001101111 操作 1
0000000111 操作 4
0000001010 操作 7
0000010000 操作 6
最后,有1盏灯仍然亮着。这是借助这个干草叉所能得到的最佳结果。当然,可行操作还有很多(最后剩下的灯可能不同)。