Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
765. Copying DNA
Олимпиадные задачи на английском языке| 04/02/2008 | Зима 2008 дорешивание (2D) |
| 05/02/2008 | Тренировка (задачи Nordic CPC 2007) (D) |
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
