시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
The company has produced an Automatic Control Machine (ACM for short) that is very popular. Due to its complete and powerful features, the company is preparing to redesign after years of sales. The new version of the ACM is still subject to a number of tests to determine the reliability of the product before it goes on the market. Because there are so many features, each test dataset can only detect several of them. Of course, the product must be available after all features have been tested. Since each test has time and material costs, they like to do the test as less as possible. Assume that running each test dataset costs the same, your job is finding the minimum number of test datasets that can cover the test of all features. For example, if there are 5 features that need to be tested, and there are 6 test datasets each can cover the features as follows:
Although {a, b, c} may do the job, but {c, d} will do the job better in the way of saving time
and money.
The first line of the input file contains one positive integer T representing the number of machines. For each machine, the first line consists of two integers n and m representing the features of machine that has to be tested and the number of test datasets. It follows by m lines, each line has a binary string of length n, showing whether the features can be detected by the test dataset or not (1 means yes, 0 means no).
Output T lines. Each of them should be the minimum number of test dataset needed to test all features for that machine. If it is not possible to test all functions for the machine, output -1.
5 3 3 100 011 111 5 6 10000 01001 01110 00111 10110 00101 6 7 000010 011000 100100 001000 000010 010000 110001 7 6 1001001 1001000 0001101 0010110 0110011 0100001 2 1 01
1 2 4 3 -1
ICPC > Regionals > Asia Pacific > Taiwan > 2019 ICPC Asia Taipei-Hsinchu Regional J번