- Mã:
- GENOME
- Tên:
- GENOME (OLP chuyên 2010)
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- thuthq
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ụ
-
input4 3
AAAAAAAAATAAAATAAAAAAAAAAAAATG
AAAAAAAAAAAAAAAAAAAATAAATGAAAA
AAAAAAAAAAAAAAAAAAATGAAAAAAAAA
AAAAAAAAAAAAATGAAAAAAAGGGGAAAAoutput15
Đoạn tin tưởng dài nhất là: AAAAAAAAAAAAATG xuất hiện trong chuỗi 1,3 và 4.
Theme :
Mời bạn soạn code
#include<bits/stdc++.h>using namespace std;int main(){ int ngay,thang,n...