Problem H
Doublets
Um doublet é um par de palavras que têm uma única letra diferente; por exemplo “booster” e “rooster”; “rooster” e “roaster”; ou “roaster” e “roasted”.
Você receberá um dicionário com até $25\, 143$ palavras em minúsculas. Nenhuma delas terá mais de $16$ letras. Você receberá vários pares de palavras. Para cada par de palavras, encontre a sequência mais curta de palavras que comece com a primeira palavra e termine com a segunda, de modo que cada par de palavras adjacentes seja um doublet. Por exemplo, se você receber o par “booster” e “roasted”, uma solução possível seria: (“booster”, “rooster”, “roaster”, “roasted”) desde que todas essas palavras estejam no dicionário.
Entrada
A entrada consiste no dicionário (com no máximo $25\, 143$ palavras) seguido por vários pares de palavras (no máximo $10$). O dicionário consiste em várias palavras, uma por linha, com uma linha em branco no final. Os pares de entrada de palavras se seguem; as palavras de cada par estão em uma linha, separadas por um espaço.
Saída
Para cada par de entrada, escreva um conjunto de linhas começando com a primeira palavra e terminando com a última. Cada par de linhas adjacentes deve ser um doublet. Se houver várias soluções mínimas, basta uma. Se não houver uma solução, simplesmente escreva na linha: “No solution.” Deixe uma linha em branco entre os casos.
| Exemplo de entrada 1 | Exemplo de saída 1 |
|---|---|
booster rooster roaster coasted roasted coastal postal booster roasted coastal postal |
booster rooster roaster roasted No solution. |