VOI 12 Bài 1 - Khoảng cách Hamming

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI 2012
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Các phân tử trong tế bào sinh học được cấu tạo từ 4 loại nuclêôtit cơ bản ký hiệu bởi các chữ cái ~A, X, T, G~. Mỗi gen di truyền được cấu tạo thành bởi một chuỗi các nuclêôtit với độ dài được tính bằng số lượng nuclêôtit. Ví dụ, ~AXXTTGAT~ là một gen có độ dài ~8~.

Trong một chuyến đi khảo sát, Giáo sư Altein phát hiện ra một gen lạ gồm ~n~ nuclêôtit được xếp trên một vòng tròn. Ngay lập tức, Giáo sư Altein dự định tiến hành so sánh gen lạ này với một số gen mẫu đang lưu trữ nhằm tìm hiểu xem mẫu gen này có gần gũi với loại gen mẫu nào đã được biết. Trong sinh học để đo độ khác biệt giữa hai mẫu gen người ta thường tính khoảng cách Hamming giữa chúng. Khoảng cách Hamming giữa hai gen cùng độ dài được định nghĩa là số lượng vị trí mà tại đó hai gen chứa các nuclêôtit khác nhau. Ví dụ, hai gen ~AGGTT~ và ~TGATT~ có khoảng cách Hamming bằng ~2~ do ~2~ nuclêôtit ở các vị trí ~1~ và ~3~ của chúng là khác nhau. Do các gen mẫu được sử dụng đều có độ dài ~m~ ~\left(m \leq n\right)~ và có cấu trúc thẳng, trong khi gen lạ lại có độ dài ~n~ và có cấu trúc vòng nên Giáo sư Altein đã định nghĩa khoảng cách Hamming giữa một gen mẫu và gen lạ là số nhỏ nhất trong số các khoảng cách Hamming giữa gen mẫu và những đoạn gen gồm ~m~ nuclêôtit liên tiếp theo chiều kim đồng hồ trong gen lạ.

Yêu cầu : Cho ~k~ gen mẫu, hãy xác định gen mẫu với khoảng cách Hamming đến gen lạ là nhỏ nhất và đưa ra khoảng cách tìm được.

Input

  • Dòng thứ nhất chứa ba số nguyên dương ~n, m, k~ ~\left(m \leq n \leq 1000;\text{ } k \leq 100\right)~.
  • Dòng thứ hai chứa xâu độ dài ~n~ là dãy các nuclêôtit của gen lạ được liệt kê theo chiều kim đồng hồ bắt đầu từ một vị trí nào đó.
  • Dòng thứ ~i~ trong số ~k~ dòng tiếp theo chứa xâu độ dài ~m~ biểu diễn gen mẫu thứ ~i~.

Output

Ghi ra một số nguyên là khoảng cách Hamming nhỏ nhất tìm được.

Giới hạn

~50\%~ số tests ứng với ~50\%~ số điểm của bài có ~n \leq 100~.

Sample Input

7 3 2
GTAAXXT
GAT
TTT

Sample Output

1

Comments

Please read the guidelines before commenting.



  • 2
    CODING   commented on Aug. 12, 2021, 1:48 p.m.

    Mn tham khảo: https://www.youtube.com/watch?v=epbCzPsNNzY&t=107s