Submit solution
Points:
0.40 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trong thành phố ~Bedao~, các nhà khoa học đã tìm thấy được ~N~ viên đá phát sáng, mỗi viên được phân biệt dựa trên ~K~ tính chất của viên đá đó. Người ta định nghĩa sự giống nhau giữa viên đá ~A~ và ~B~ bằng phép XNOR được thể hiện qua bảng dưới đây:

Các nhà khoa học muốn tạo ra một viên đá mới sao cho sự giống nhau lớn nhất giữa viên đá mới và ~N~ viên đá đã được tìm thấy là bé nhất.
Input
- Dòng đầu tiên gồm hai số ~N~, ~K~ lần lượt là số lượng viên đá phát sáng và số tính chất của tất cả các viên đá đó ~(1 \le N \le 10^5, 1 \le K \le 20)~.
- ~N~ dòng tiếp theo, mỗi dòng chứa một dãy nhị phân biểu diễn tính chất của viên đá đó
Output
- Một số nguyên duy nhất là kết quả của bài toán.
Sample Input
3 6
110111
011000
111110
Sample Output
3
Note
- Giả sử viên đá mới có tính chất là ~110001~, kết quả sẽ là ~max(4, 3, 2) = 4~
- Nhưng nếu viên đá mới có tính chất là ~100000~ thì kết quả sẽ là ~max(2, 3, 2) = 3~.
- Như vậy kết quả của ví dụ trên sẽ là ~3~ và ta có thể chứng minh nó là đáp án tối ưu nhất.
Subtask
- ~30\%~ số test có ~N \le 10~
- ~30\%~ số test tiếp theo có ~N \le 10^3~
- ~40\%~ số test còn lại không có điều kiện gì thêm.
Comments