#P2724. Purifying Machine
Purifying Machine
描述
Mike 是一家奶酪厂的老板,他有 块奶酪,每块奶酪都被分配了一个二进制编号,从 到 。为了保证奶酪不被病毒感染,他制造了一台净化机来清理被病毒感染的奶酪。这台净化机设计得很特殊:它有 个开关,每个开关有三种状态,分别为 、 和 。
一次操作就是根据这 个开关的状态进行一次清理动作。在一次操作中,最多只能有一个开关处于 状态,该状态可以代替 或 。当净化机被调到某一特定状态时,将会清理与该二进制状态对应的所有奶酪。
例如,如果 ,开关状态为 ,则该操作会清理编号为 和 的奶酪。
一天,Mike 的机器被感染了。当 Mike 发现时,他已经对奶酪进行了一些操作,结果操作过的奶酪也都被感染。Mike 迅速清理了机器,但现在他需要用最少的操作次数清理掉所有受感染的奶酪。
清理时要求:
- 如果一块奶酪是被感染的,那么用机器对该奶酪操作一次或多次就能使其复原;
- 如果奶酪没有被感染,操作它会使奶酪变坏。
给定 Mike 已经做过的感染操作,求必须再进行的最少操作次数,使得所有被感染的奶酪都能清理,而不会使未感染的奶酪变坏。
输入
输入包含若干测试用例。
每个测试用例的第一行包含两个整数 和 ,其中 表示开关数量, 表示 Mike 已经做过的感染操作次数。
接下来的 行,每行给出一个长度为 的字符串,表示一次感染操作时机器的开关状态。
测试用例以一行 "" 结束,不处理此测试用例。
输出
对于每个测试用例,输出一行一个整数,表示 Mike 还需要进行的最少操作次数。
3 3
*01
100
011
0 0
2
题目来源
Beijing 2005