THT Bình Định 2023 - VIRUS

View as PDF

Submit solution


Points: 500.00 (partial)
Time limit: 0.75s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem source:
THT BDi 2023
Problem type

Có nhiều loại virus có hại cho sức khỏe của con người (như virus sởi, quai bị, dại,...). Vì thế các nhà khoa học luôn không ngừng bỏ cuộc, tìm cách để tiêu diệt những chủng virus đó. Để có thể hiểu sâu hơn về chúng, họ cần tìm cách để tổng hợp những virus trên.

Ta được cho một xâu gồm các chữ cái A, G, TC. Dãy kí tự này tương ứng với trình tự nucleotide DNA của virus cần tổng hợp. Ta bắt đầu với một xâu rỗng, và được sử dụng các thao tác sau:

  1. Thêm một nucleotide vào đầu hoặc cuối xâu hiện có.
  2. Sao chép xâu, đảo ngược đoạn đã sao chép và dán nó vào đầu hoặc cuối xâu ban đầu (ví dụ: AGTC có thể trở thành AGTCCTGA hoặc CTGAAGTC).

Một xâu có thể được tạo từ một chuỗi gồm nhiều thao tác. Tuy nhiên, ta cũng cần phải quan tâm đến hiệu quả. Vì vậy, hãy tìm cách tổng hợp virus sao cho số thao tác được sử dụng là nhỏ nhất.

Input

  • Dòng đầu tiên gồm một số nguyên dương ~T~, là số lượng bộ dữ liệu.
  • ~T~ dòng tiếp theo, mỗi dòng gồm một xâu kí tự ~S_i~ khác rỗng, chi bao gồm các chữ in hoa A, G, TC.

Output

  • Gồm ~T~ dòng, dòng thứ ~i~ gồm một số nguyên dương là số thao tác nhỏ nhất được sử dụng để có thể xây dựng được xâu ~S_i~.

Sample Input

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

Sample Output

3
8
6
18

Giải thích test mẫu:

Cách xây dựng xâu tối ưu cho từng bộ dữ liệu như sau:

  1. ~\emptyset~ → AAAAAAA.
  2. ~\emptyset~ → AAGAGCAGCTAGCTTAGCTTGAGCTTGCAGCTTGCAA.
  3. ~\emptyset~ → AGAGGAAGGGGAAAGGGGAAAGGGGAAGGGGAA.
  4. ~\emptyset~ → AAAAAAAAAAAAAAAAAACCAAAAAAAAAAAAC rồi thêm những kí tự còn lại vào xâu bằng thao tác ~(1)~.

Scoring

Subtask Điểm Giới hạn
~1~ ~20 \%~ ~|S_i| \leq 700~, với mọi bộ dữ liệu
~2~ ~80 \%~ ~|S_i| \leq 5 \times 10^4~, với mọi bộ dữ liệu

Comments

Please read the guidelines before commenting.


There are no comments at the moment.