Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 17 24 de maio
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #08]
Um coleccionador de livros raros
descobriu recentemente um livro escrito numa língua pouco familiar mas
que usa o mesmo conjunto de caracteres usados na língua inglesa. O
livro possui um pequeno índice, contudo a ordem dos itens do índice é
diferente da que se esperaria encontrar caso os caracteres estivessem
ordenados da mesma forma que no alfabeto inglês (composto por 26
letras). O coleccionador tentou usar o índice para determinar a ordem
dos caractéres (i.e. a sequência de junção) do alfabeto estranho, mas
acabou por desistir atendendo a que a tarefa se revelava frustante e
fastidiosa.
O índice é constituído por um conjunto de palavras que sabemos que vêm ordenadas na "ordem que queremos descobrir". Por exemplo, o indíce poderia ser:
XWY ZX ZXY ZXW YWWX
Com isto consegue-se descobrir as relações entre letras. Por exemplo, como a palavra XWY vem antes de ZX, sabemos que na língua do livro a letra 'X' vem antes da letra 'Z'. Sabemos também que a letra 'Y' vem depois de 'Z' porque ZXW aparece antes de YWWX. Finalmente, sabemos que a letra 'W' vem depois de 'Y', porque a palavra ZXW vem depois de ZXY.
Com todas estas considerações, sabemos que a ordem correcta das letras da lingua "estranha" só pode ser XZYW.
A tua tarefa é escrever um programa para completar o trabalho do coleccionador. Em particular, o teu programa deverá receber um conjunto de palavras ordenadas associadas a uma dada sequência de ordem das letras e determinar qual é essa sequência.
Na primeira linha vem um número inteiro N indicando o número de palavras a ler. Seguem-se N linhas, cada uma com uma palavra Pi contendo apenas letras maiúsculas.
As linhas vêm ordenada pela ordem que pretende descobrir.
Deve ser imprimida uma única linha contendo as letras maiúsculas na ordem determinada pela sequência de junção usada para produzir o input. Apenas devem aparecer os caracteres que aparecem no input.
Para os casos de teste dados, é garantido que existe uma e só uma ordem para a qual o input faz sentido.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ N ≤ 100 | Número de palavras | |
1 ≤ |Pi| ≤ 10 | Tamanho de cada palavra |
5 XWY ZX ZXY ZXW YWWX
XZYW
Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto