提示: 欢迎访问OurACM平台。
Problem 1594 冗余编码

Accept: 262    Submit: 638
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

分布式系统常采用“冗余编码”来容错。一个拥有n个结点的分布式系统将一个文件分成m个文件块,每个结点拥有其中若干文件块(同一文件块可能被多个结点拥有,正所谓“冗余”)。当需要使用时,系统可以从各结点获取所需的文件块,组成完整的文件。

但在分布式系统中,结点的失效是不确定的,当其中k个结点保持正常工作,系统一定能获取完整的文件,而当其中k-1个结点正常工作时候,系统可能无法获取完整的文件,则称该分布式系统是k-可靠的。

Input

本题有多组输入数据,你必须处理到EOF为止。

每组数据第一行是两个正整数n,m (n<=100, m<=15),接下来是n*m个01串,第i行第j列表示第i个结点是否拥有第j个文件块(0表示没有,1表示拥有)。

Output

仅一行一个正整数k。

Sample Input

5 4 1111 1001 0110 1010 0101

Sample Output

3

Hint

结点2和结点4都缺少文件块2,无法组成完整的文件,所以k>2;而任意3个结点都能组成完整的文件,所以k=3。

Source

福州大学第五届程序设计竞赛

Submit  Back  Status  Discuss