trang chủ / đề bài / icpc26_mn_h

Khôi phục DNA

Đề bài

Mô tả

Trong tin sinh học, các nhà khoa học thường nghiên cứu DNA thông qua những đoạn ngắn có cùng độ dài, gọi là các K-mer. Một xâu DNA là xâu chỉ gồm bốn ký tự A, C, G và T.

Một xâu DNA có độ dài L≥K sinh ra L−K+1 xâu con liên tiếp độ dài K, bắt đầu tại các vị trí 1,2,…,L−K+1. Ví dụ, với K=3, xâu ACGTA sinh ra ba K-mer: ACG, CGT và GTA.

Sau một thí nghiệm giải trình tự, các nhà khoa học thu được N đoạn DNA đôi một phân biệt S1,S2,…,SN, mỗi đoạn có độ dài đúng bằng K. Họ muốn khôi phục một xâu DNA ngắn nhất từ các đoạn này.

Một xâu DNA T được gọi là hợp lệ nếu thỏa mãn cả hai điều kiện sau:

  • mọi Si (1≤i≤N) xuất hiện ít nhất một lần dưới dạng xâu con liên tiếp của T;
  • mọi xâu con liên tiếp độ dài K của T đều thuộc tập {S1,S2,…,SN}.

Như vậy, một đoạn Si có thể xuất hiện trong T nhiều lần, nhưng không được có K-mer nào nằm ngoài danh sách đã cho xuất hiện trong T.

Ngoài ra, do giới hạn lưu trữ, độ dài của T không được vượt quá

N+K−1+R,

trong đó R là một số nguyên không âm cho trước.

Hãy tìm độ dài nhỏ nhất của một xâu DNA hợp lệ có độ dài không vượt quá giới hạn trên. Nếu không tồn tại xâu như vậy, in ra −1.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên N, K và R (1≤N≤2·105, 2≤K≤12, 0≤R≤15).
  • Dòng thứ i trong N dòng tiếp theo chứa xâu Si có độ dài đúng bằng K và chỉ gồm các ký tự A, C, G và T.

Các xâu S1,S2,…,SN đôi một phân biệt.

Dữ liệu ra

In ra một số nguyên: độ dài nhỏ nhất của một xâu DNA hợp lệ có độ dài không quá N+K−1+R, hoặc −1 nếu không tồn tại xâu như vậy.

Ràng buộc

  • 1≤N≤2·105.
  • 2≤K≤12.
  • 0≤R≤15.
  • Mỗi Si có độ dài K, chỉ gồm A, C, G, T; các Si đôi một phân biệt.

Ví dụ

Input Output Giải thích
5 2 1
AC
AG
AT
CG
GA
7 Xâu ACGAGAT có độ dài 7 và chứa cả năm đoạn đã cho; đoạn GA xuất hiện trong nó hai lần. Không có xâu hợp lệ nào độ dài 6.
5 2 0
AC
AG
AT
CG
GA
-1 Cần ít nhất 7 ký tự để tạo được một xâu hợp lệ, trong khi giới hạn độ dài là 5+2−1+0=6.
2 3 9
ACT
GGA
-1 Không có xâu nào chứa được cả hai đoạn đã cho mà không chứa thêm một 3-mer nằm ngoài danh sách.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0