Copying DNA

View as PDF

Submit solution

Points: 1.70 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
NCPC 2007
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~.

Input

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~.

Output

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.

Sample Input

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

Sample Output

2
impossible
1
4
6

Comments

Please read the guidelines before commenting.


There are no comments at the moment.