[Usaco2006 Mar]Lights Out 关灯

时间限制:5s      空间限制:64MB

题目描述

奶牛们喜欢在黑暗中睡觉。每天晚上,他们的牲口棚有L(3<=L<=50)盏灯,他们想让亮着的灯尽可能的少。他们知道按钮开关的位置,但喜闻乐见的是他们并没有手指。你得到了一个长度为T(1<=T<=7)的插槽用以帮助奶牛们改变灯的状态。


输入格式

第一行,两个整数L和T。第二行给出一个长度为L的01串表示初始灯的状态,0表示灯是灭的,1表示灯是亮的。第三行给出一个长度为T的01串,表示你获得的插槽。


输出格式

第一行输出一个整数K,表示在满足亮着的灯最少的情况下,你要用插槽操作的次数。第二行到第K+1行,每行一个整数表示你的插槽使用的位置。
"K最小的解,并且满足解的字典序最大(即按钮开关的位置尽可能靠后)"


样例输入

10 4
1111111111
1101

样例输出

5
1
3
4
6
7


提示

使用5次插槽
1111111111  初始状态
0010111111  对第一个位置使用插槽
0001101111  对第三个位置使用插槽
0000000111  对第四个位置使用插槽
0000011101  对第六个位置使用插槽
0000010000  对第七个位置使用插槽
可以证明这是满足字典序最小的最优解。


题目来源

Silver

Menuappsclose