GEN - GENOME (OLP 2010)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 10.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

DNA là thành phần cơ bản cấu tạo thành bộ genome của sinh vật. DNA bao gồm 4 loại khác nhau là {A,X,T,G}. Để nghiên cứu các sinh vật ở mức độ phân tử, người ta tiến hành giải mã bộ genome của chúng.

Để giải mã bộ genome của một sinh vật, máy giải mã thế hệ mới sẽ sinh ra N đoạn cơ sở, mỗi đoạn cơ sở là một dãy bao gồm 30 DNA. Các đoạn cơ sở sẽ được ghép nối với nhau để tạo thành một bộ genome hoàn chỉnh.

Ta nói một đoạn DNA X được bao phủ bởi một đoạn cơ sở Y nếu tồn tại một đoạn của Y trùng với X. Giả sử k là một số nguyên dương, một đoạn DNA X được gọi là đoạn tin tưởng cấp k nếu X được bao phủ bởi ít nhất k đoạn cơ sở.

Yêu cầu: Cho N đoạn cơ sở và số nguyên dương k, hãy tìm đoạn tin tưởng cấp k có độ dài lớn nhất.

Dữ liệu nhập:

- Dòng đầu chứa hai số nguyên dương N và k (0< k ≤ N ≤ 30.000)

- N dòng tiếp theo, mỗi dòng chứa một đoạn cơ sở.

Dữ liệu xuất:

- Là một số nguyên xác định độ dài của đoạn tin tưởng tìm được (ghi -1 nếu không tồn tại đoạn tin tưởng cấp k)

Ví dụ

  • input
    4 3
    AAAAAAAAATAAAATAAAAAAAAAAAAATG
    AAAAAAAAAAAAAAAAAAAATAAATGAAAA
    AAAAAAAAAAAAAAAAAAATGAAAAAAAAA
    AAAAAAAAAAAAATGAAAAAAAGGGGAAAA
    output
    15

Đoạn tin tưởng dài nhất là: AAAAAAAAAAAAATG xuất hiện trong chuỗi 1,3 và 4.

http://www.olp.vn/luu-tru/2010/de-thi/DethiKhoiChuyenTin_OLP2010.pdf?attredirects=0&d=1

Back to Top