printРабочее место участника

printЗадачи

765. Copying DNA

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard combinatorial problems. You are now to do something completely different. Given a DNA string `S` from the alphabet {A,C,G,T}, find the minimal number of copy operations needed to create another string `T`. You may reverse the strings you copy, and copy both from `S` and the pieces of your partial `T`. You may put these pieces together at any time. You may only copy contiguous parts of your partial `T`, and all copied strings must be used in your final `T`. Example: From `S` = "ACTG" create `T` = "GTACTATTATA"
  • Get GT......... by copying and reversing "TG" from `S`.
  • Get GTAC....... by copying "AC" from `S`.
  • Get GTAC...TA.. by copying "TA" from the partial `T`.
  • Get GTAC...TAAT by copying and reversing "TA" from the partial `T`.
  • Get GTACAATTAAT by copying "AAT" from the partial `T`.
Input specifications
The first line of input gives a single integer, `1\ ≤\ t\ ≤\ 100`, the number of test cases. Then follow, for each test case, a line with the string `S` of length `1\ ≤\ m\ ≤\ 18`, and a line with the string `T` of length `1\ ≤\ n\ ≤\ 18`.
Output specifications
Output for each test case the number of copy operations needed to create `T` from `S`, or "impossible" if it cannot be done.

Sample input

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

Output for sample input

2
impossible
1
4
6
Source: Nordic CPC 2007
loading