COPYDNA - Copying DNA

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/copydna


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

Added by:Jimmy
Date:2008-10-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NCPC 2007

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.