Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HAM12 - VOI 2012 Khoảng cách Hamming

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ham12


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 (m ≤ n) 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.

Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.

Input

  • Dòng thứ nhất chứa ba số nguyên dương n, m, k (m ≤ n ≤ 1000; k ≤ 100).
  • 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.

Example

Input:
7 3 2
GTAAXXT
GAT
TTT Output: 1

Được gửi lên bởi:VOJ Team
Ngày:2012-01-18
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2020-09-01 15:44:15
0,37s trau ac
2019-09-23 11:28:18
admin đtrai ơi cho em acc đi :(( bao phòng
2019-09-23 11:25:07
em xin loi a
2019-09-23 11:24:45
dm đổi admin đi
2019-09-23 11:23:20
n*m*k del acc ?? test oc cho ak
2018-12-28 15:20:56
bruteforce 1 múc cx AC trong 0.28s, lúc đầu cứ nghĩ sẽ bị TLE :))
2017-12-27 03:26:21
Trâu cũng AC =))))
frostpixel aka.How 2 AC
2017-12-16 07:49:28
kì vậy ta , O(m*N*K) là sao vẫn AC, có 0,4s chứ mấy
2017-08-17 16:30:55
trâu AC ez :)
2017-07-24 06:18:26
Xem code ở https://vietcodes.github.io/code/23

Last edit: 2017-08-06 10:56:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.