시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 195 | 59 | 48 | 30.000% |
You are given a set of N integer sequences Z = {Z1, Z2, ··· , ZN}, where |Zi| = K for i = 1, 2, ··· , N.
The N integer sequences in the set were generated by the following generation process:
For example, an integer sequence Zi = {1, 0, 1, 2, 2} can be generated by two binary sequences X = {1, 0, 0, 1, 1} and Y = {0, 0, 1, 1, 1}.
Given N integer sequences generated, write a program to find how many elements in the set B. If there are several possible solutions, find the one with minimum set size.
The first line of the input contains two integers K and N (1 ≤ K ≤ 20, 1 ≤ N ≤ 24). A whitespace character separates those two numbers. Each of the following N lines contains elements of Z. The jth number in the i-th line represents Zi,j, the value of the j-th element of Zi. There are no delimiter characters between adjacent numbers in these N lines.
Print the minimum number of elements in the set B.
5 2 10122 20022
2
In the sample, we can generate each element in the set Z by letting X = {1, 0, 0, 1, 1}, Y = {0, 0, 1, 1, 1} and X = {1, 0, 0, 1, 1}, Y = {1, 0, 0, 1, 1}, respectively. Therefore, Z can be constructed by the set B = {{1, 0, 0, 1, 1} and {0, 0, 1, 1, 1}}.