Problem H
Dobletes
Languages
en
es
fr
pt
Un Doblete es un par de palabras que difieren en una sola letra; por ejemplo, “booster” y “rooster” o “rooster” y “roaster” o “roaster” y “roasted”.
Se pone a su disposición un diccionario de hasta $25\, 143$ palabras en minúsculas, con un máximo de $16$ letras cada una. Luego se le da una serie de pares de palabras. Para cada par de palabras, encuentre la secuencia más corta de palabras que empiecen con la primera palabra y termine con la segunda, de tal manera que cada par de palabras adyacentes sea un doblete. Por ejemplo, si le dan como enunciado el par de palabras “booster” y “roasted”, una posible solución sería: (“booster”, “rooster”, “roaster”, “siempre que todas estas palabras estén en el diccionario.
Enunciado
El enunciado está formado por el diccionario (con un máximo de $25\, 143$ palabras) seguido de un número de pares de palabras (como máximo $10$). El diccionario consiste en una serie de palabras, una por línea, seguida de una línea vacía. A continuación, se le dan los enunciados, formados por pares de palabras; las palabras de cada par se colocan en una misma línea separadas por un espacio.
Solución
Para cada par de palabras del enunciado, imprima un conjunto de líneas que empiecen con la primera palabra y terminen con la última. Cada par de líneas adyacentes debe ser un doblete. Si hay varias soluciones mínimas, cualquiera de ellas será válida. Si no hay solución, imprima una línea con el siguiente texto: “No solution.” Deje una línea en blanco entre cada caso.
| Ejemplo de enunciado 1 | Ejemplo de solución 1 |
|---|---|
booster rooster roaster coasted roasted coastal postal booster roasted coastal postal |
booster rooster roaster roasted No solution. |