| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MGENOME - GENOME |
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,C,G,T}. Để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ở Ynếu tồn tại một đoạn liên tiếp
trong Ytrùng với X. Giả sử k là 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: Vào từ file văn bản GENOME.INP có cấu trúc nhưsau:
Dòng đầu chứa hai sốnguyên dương N và k(0 < k ≤ N ≤30000);
Mỗi dòng trong Ndòng tiếp theo chứa một đoạn cơ sở.
Kết quả: Đưa ra file văn bản GENOME.OUT một số nguyên là độ dài của đoạn tin tưởng
tìm được. (Ghi số -1 nếu không tồn tại đoạn tin tưởng cấp k).
Ví dụ:
GENOME.INP
4 3
AAAAAAAAATAAAATAAAAAAAAAAAAATG
AAAAAAAAAAAAAAAAAAAATAAATGAAAA
AAAAAAAAAAAAAAAAAAATGAAAAAAAAA
AAAAAAAAAAAAATGAAAAAAAGGGGAAAA
GENOME.OUT
15
Lưu ý:50% sốtest có N ≤1000 tương ứng với 50% tổng số điểm dành cho bài.
| Được gửi lên bởi: | psetter |
| Ngày: | 2014-10-20 |
| Thời gian chạy: | 0.100s-3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
| Nguồn bài: | CT 2010 |
hide comments
