trang chủ / đề bài / icpcwf20_d

Gấp gen

Đề bài

Mô tả

Công ty Xử lý Tế bào Quốc tế (ICPC) là công ty hàng đầu thế giới về phân tích chuỗi gen. Một chuỗi gen là một dãy các nucleotide; trong bài này nó được biểu diễn bằng một xâu chỉ gồm các chữ cái A, C, G và T theo một tổ hợp nào đó, mỗi chữ cái biểu diễn một nucleotide (lần lượt là Adenine, Cytosine, Guanine và Thymine).

Một trong những phát hiện quan trọng của ICPC là thông qua một quá trình gọi là Gấp Hữu cơ Tối ưu hóa Di truyền (GOOF), họ có thể biến một chuỗi gen thành một chuỗi đơn giản hơn mà vẫn giữ được nhiều tính chất của chuỗi mà ICPC muốn phân tích.

Một lần áp dụng GOOF diễn ra như sau. Tìm một điểm nằm giữa hai nucleotide kề nhau trong chuỗi sao cho chuỗi đọc từ điểm đó theo cả hai hướng là giống nhau, cho tới đầu gần hơn của chuỗi. Ví dụ, chuỗi ATTACC có hai điểm như vậy: AT-TACC và ATTAC-C. Sau đó chọn một trong các điểm này (chẳng hạn điểm thứ nhất) và gấp chuỗi gen tại điểm đó, gộp các nucleotide trùng nhau (ở ví dụ này, AT và TA được gộp lại, và chuỗi thu được là CCAT hoặc TACC).

Áp dụng GOOF nhiều lần có thể làm một chuỗi ngắn đi rất nhiều. Tuy nhiên, việc tìm các điểm gấp thích hợp bằng tay rất tốn thời gian. ICPC nhờ bạn viết chương trình tự động tìm các điểm gấp và chọn chúng sao cho thu được chuỗi gen ngắn nhất có thể từ chuỗi đầu vào.

Dữ liệu vào

Một dòng duy nhất chứa xâu s là chuỗi nucleotide cần phân tích. Xâu chỉ gồm các ký tự A, C, G và T.

Dữ liệu ra

In ra độ dài nhỏ nhất có thể của một chuỗi thu được từ chuỗi đầu vào bằng cách áp dụng GOOF không hoặc nhiều lần.

Ràng buộc

  • 1≤|s|≤4·106.

Ví dụ

Input Output Giải thích
ATTACC 3 Gấp tại AT-TACC được TACC, sau đó gấp tại TAC-C được TAC (độ dài 3). Không còn điểm gấp nào.
AAAAGAATTAA 5 Gấp ba lần tại điểm giữa hai chữ A đầu tiên: AAAAGAATTAA thành AAAGAATTAA, AAGAATTAA, rồi AGAATTAA. Sau đó gấp tại AGAAT-TAA được AGAAT (độ dài 5).

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