Trabalhas
como programador num estação televisiva, e tens de ajudar a gerar
automaticamente os puzzles de um concurso. Entre eles está o das
Pirâmides de Palavras, onde os concorrentes tentam adivinhar as
letras em falta de uma dada pirâmide de palavras.
Muito resumidamente, uma Pirâmide de Palavras é uma sequência de palavras onde cada palavra usa exactamente as mesmas letras da palavra anterior, ainda que possam (ou não) aparecer por ordem diferente, mais uma nova letra, em qualquer posição. Assim, o comprimento de cada palavra é superior em uma unidade ao comprimento da palavra anterior. Por exemplo, uma pirâmide válida seria:
a ra mar ramo morar
Os gestores do concurso gostam de aproveitar os temas da actualidade para gerar as pirâmides e por isso todos os dias querem poder escolher uma palavra para meter na pirâmide. Estão também interessados em gerar a maior pirâmide possível, para dificultar o puzzle.
Tens disponível um dicionário contendo todas as palavras consideradas válidas. Dada a palavra a incluir na pirâmide, tens de criar um programa que descubra a maior pirâmide de palavras possível.
Dada uma palavra P e um dicionário com N palavras (uma das quais é P), a tua tarefa é calcular qual a maior pirâmide possível que inclua a palavra P. Por maior pirâmide de palavras entende-se a que use o maior número de palavras que for possível. Todas as palavras da pirâmide têm de existir no dicionário.
Na primeira linha do input vem uma palavra P, constituída unicamente por letras minúsculas simples (sem acentos ou cedilhas).
Na segunda linha vem um único número inteiro N representando o número de palavras no dicionário. Seguem-se exactamente N linhas, cada uma delas representando uma das palavras do dicionário. Estas palavras podem vir por qualquer ordem e tal como a palavra inicial contêm apenas letras minúsculas simples.
A primeira linha do output deve apresentar um único inteiro M indicando a altura da maior pirâmide possível que inclua a palavra P. Nota que essa palavra pode aparecer em qualquer posição da pirâmide e que a pirâmide não tem necessariamente de começar numa palavra de tamanho um.
Devem seguir-se exactamente M linhas detalhando essa pirâmide, uma palavra por linha, da mais pequena para a maior. Se existirem várias possibilidades para a maior pirâmide, deves escolher aquela que for alfabeticamente menor, isto é, aquela que resulta na palavra alfabeticamente menor quando todas as palavras da pirâmide são concatenadas (juntas), começando da mais curta para a mais comprida.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 10 000 | Número de palavras do dicionário | |
| Todas as palavras terão um comprimento inferior ou igual 30 letras | ||
Para um conjunto de casos de teste valendo 60% dos pontos, o número de palavras do dicionário é inferior a 100.
mar 10 ramo fato morar ra mare a mar olimpiadas pa morada
5 a ra mar ramo morar
oni 8 a no finos afino fino oni ao afinas
4 no oni fino afino