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.
O Problema
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.
Input
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.
Output
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.
Restrições
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
Nota sobre a avaliação
Para um conjunto de casos de teste valendo 60% dos pontos, o número de palavras do dicionário é inferior a 100.
Exemplo de Input 1
mar
10
ramo
fato
morar
ra
mare
a
mar
olimpiadas
pa
morada
Exemplo de Output 1
5
a
ra
mar
ramo
morar
Exemplo de Input 2
oni
8
a
no
finos
afino
fino
oni
ao
afinas
Exemplo de Output 2
4
no
oni
fino
afino
Editado por quintelab Título alterado conforme as regras do fórum
Pergunta
chulos
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.
O Problema
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.
Input
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.
Output
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.
Restrições
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
Nota sobre a avaliação
Para um conjunto de casos de teste valendo 60% dos pontos, o número de palavras do dicionário é inferior a 100.
Exemplo de Input 1
mar
10
ramo
fato
morar
ra
mare
a
mar
olimpiadas
pa
morada
Exemplo de Output 1
5
a
ra
mar
ramo
morar
Exemplo de Input 2
oni
8
a
no
finos
afino
fino
oni
ao
afinas
Exemplo de Output 2
4
no
oni
fino
afino
Editado por quintelabTítulo alterado conforme as regras do fórum
Link para o comentário
Compartilhar em outros sites
2 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.