Bedao Mini Contest 10 - STONE

View as PDF

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

Please read the guidelines before commenting.


There are no comments at the moment.