COPYDNA - Copying DNA

Cho một xâu DNA S gồm các ký tự {A, C, G, T}. Bạn sẽ làm việc trên một xâu T, ban đầu có giá trị rỗng. Tìm số thao tác sao chép nhỏ nhất để biến T thành một xâu cho trước. Biết rằng mỗi thao tác sao chép có một trong hai dạng:

  • sao chép S i j k: sao chép đoạn S[i..j] vào xâu T bắt đầu từ vị trí k
  • sao chép T i j k: sao chép đoạn T[i..j] vào xâu T bắt đầu từ vị trí k

Lưu ý nếu i > j có nghĩa là ta sao chép đoạn xâu theo thứ tự ngược. Mỗi ký tự trong T chỉ được tạo ra đúng một lần, nghĩa là không được sao chép đè lên ký tự đó.

Ví dụ: Với S = “ACTG” hãy tạo T = “GTACTATTATA”

  1. Tạo GT......... bằng cách sao chép và đảo xâu “TG” từ S.
  2. Tạo GTAC....... bằng cách sao chép “AC” từ S.
  3. Tạo GTAC...TA.. bằng cách sao chép “TA” từ T.
  4. Tạo GTAC...TAAT bằng cách sao chép và đảo xâu “TA” từ T.
  5. Tạo GTACAATTAAT bằng cách sao chép “AAT” từ T.

Dữ liệu

Dòng đầu tiên chứa t là số bộ test. Với mỗi test có hai dòng chứa xâu S và xâu T với độ dài không quá 18.

Kết quả

Với mỗi test, in ra số thao tác sao chép ít nhất để tạo ra T từ S, hoặc in ra "impossible" nếu không thể làm được.

Ví dụ

Dữ liệu
5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

Kết quả
2
impossible
1
4
6

Được gửi lên bởi:Duc
Ngày:2008-10-01
Thời gian chạy:0.229s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:NCPC 2007

hide comments
2013-08-28 14:16:47 Mèo


Last edit: 2013-10-26 16:15:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.