CSES - Hamming Distance | Khoảng cách Hamming

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , SPyofgame
Dạng bài
Điểm: 1800 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Khoảng cách Hamming giữa hai xâu \(a\) và \(b\) có cùng độ dài chính là số lượng vị trí mà cặp xâu này khác nhau.

Bạn được cho \(n\) xâu nhị phân, có cùng độ dài \(k\) và nhiệm vụ của bạn chính là tính cái khoảng cách Hamming nhỏ nhất giữa hai xâu bất kì.

Input

Dòng đầu tiên chứa hai số nguyên là \(n\) và \(k\): số lượng xâu nhị phân và độ dài của chúng.

Sau đó gồm \(n\) dòng, mỗi dòng chứa một xâu nhị phân độ dài \(k\)

Output

In khoảng cách Hamming nhỏ nhất giữa một cặp xâu bất kì.

Constraint

  • \(2 \leq n \leq 2 \cdot 10^4\)
  • \(1 \leq k \leq 30\)

Example

Input:

5 6
110111
001000
100001
101000
101110

Output:

1

Explanation:

Cặp xâu "101000" và "001000" khác nhau chỉ duy nhất tại vị trí đầu tiên.

Bình luận


  • 1
    huyhau6a2    6:00 p.m. 29 Tháng 8, 2022

    Cho em hỏi tại sao:

    Code 1:

    for(int i=0;i<n;i++)
{
    for(int j=i-1;j>=0;j--)
    {
        //code
    }
}

    Code 2:

    for(int i=0;i<n-1;i++)
{
    for(int j=i+1;j<n;j++)
    {
        //code
    }
}

    Em code 2 vòng lặp khác nhau nhưng code 1 lại tle với bài này, code 2 lại ac, can anyone explain of this?


    • 0
      PhanHuyKhang    7:31 p.m. 29 Tháng 8, 2022

      có vẻ như -- sẽ chậm hơn với ++


      • 0
        huyhau6a2    7:59 p.m. 29 Tháng 8, 2022

        bên cses mình code cả 2 loại vòng lặp đều ac hmm?