Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PARQUE - Parque Jurássico

O DNA é uma molécula envolvida na transmissão de caracteres hereditários e na produção de proteínas, que são os principais constituintes de seres vivos. O DNA é formado pelas bases nitrogenadas adenina (A), guanina (G), citosina (C) e timina (T).

A identificação da seqüência de bases que constitui uma determinada parte do DNA pode ajudar a descoberta da cura de doenças que atacam seres vivos. Teoricamente, a identificação do DNA pode também permitir a recriação de espécies extintas, como na estória do escritor americano Michael Crichton.

O professor de Biologia de sua escola, prof. Estevão Espilbergo, conseguiu amostras de células de uma espécie de mosquito extinto a milhares de anos, e pretende, ambiciosamente, recriar o animal a partir de seu DNA. Para isso, conseguiu que um laboratório de genômica fizesse a identificação das bases das células. No entanto, pelo estado precário das células obtidas, o resultado não foi dos melhores. O professor Estevão recebeu do laboratório duas seqüências, com a informação de que essas seqüências contêm, provavelmente, muitos "buracos", ou seja, entre uma base e outra corretamente detectadas podem existir bases não detectadas.

O prof. Estevão então decidiu combinar as duas seqüências para formar uma seqüência única, e precisa de sua ajuda.

Tarefa

Sua tarefa é escrever um programa que determine a menor seqüência que contenha, como subseqüências, as duas seqüências obtidas pelo laboratório. Dizemos que uma seqüência S1 é subseqüência de uma outra seqüência S2 se acrescentando-se alguns elementos a S1 obtém-se S2. Por exemplo, ACGT é uma subseqüência de ATCGAAT, pois basta inserir um T após o A e dois A’s após o G.

Entrada

A entrada possui vários conjuntos de teste. Cada conjunto de teste é composto por duas linhas, cada uma contendo uma seqüência S composta por caracteres 'A’, 'C’, 'G’ e 'T’. O final da entrada é indicado por uma linha contendo o caractere '#’.

Exemplo de Entrada
AAATTT
GAATCT
ACGT
ATCGAAT
#

Saída

Para cada conjunto de teste, o seu programa deve escrever três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado seqüencialmente a partir de 1. A segunda linha deve conter uma seqüência de comprimento mínimo que contenha as duas seqüências da entrada como subseqüências. Se houver mais de uma seqüência de comprimento mínimo, seu programa pode escrever qualquer uma delas. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída
Teste 1
GAAATCTT

Teste 2
ATCGAAT

(esta saída corresponde ao exemplo de entrada acima)

Restrições

1 <= número de caracteres de S <= 100


Adicionado por:Wanderley Guimarăes
Data:2007-03-03
Tempo limite:0.130s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2003 - Seletiva

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