Submeter | Todas submissőes | Melhores | Voltar |
PSQF - Problemas SQF |
Juciano, Sebastião e Sérgio formavam um time da ACM muito bom. Eles costumavam resolver um monte de problemas mas eles não eram muito organizados e nunca classificavam os problemas quando os resolviam.
Dado que a Regional da América do Sul da ACM estava se aproximando, eles decidiram classificar todos os problemas que tinham resolvido. Como eles eram um time muito bom, havia centenas de problemas para classificar e eles decidiram utilizar uma abordagem sistemática para acelerar o processo.
No abordagem deles um problema seria classificado baseado em palavras-chave. Um problema de grafos, por exemplo, seria identificado por palavras como: nó, aresta, distância etc. Por outro lado, palavras típicas em problemas geométricos seriam: ponto, convexo, polígono etc.
Mas uma porção de problemas não puderam ser classificados poque eles não se enquadravam em nenhuma categoria. Coincidentemente, Sérgio foi quem resolveu todos os problemas sem classificação, porque ele gastou seu tempo tentando resolver problemas da ACM mas quase todos eram muito fáceis. Desse modo, Juciano e Sebastião decidiram classificar estes problemas sem classificação como SQF, isto é: Sérgio Que Fez.
Sua tarefa é ajudar os membros do time a classificar os problemas. Um problema pode pertencer a mais de uma categoria, se o problema não pertencer a nenhuma categoria, então ele é um problema SQF.
Entrada
O conjunto de entrada consiste de um número positivo N ≤ 30
,
que indica o número de casos de teste.
Cada caso de teste começa com um número C ≤ 20
, o número de
categorias. A seguir, cada categoria é descrita por uma cadeia de
caracteres S
, o nome da categoria, e dois inteiros
W ≤ 10
, o número de palavras-chave neste categoria, e
P
, quantas palavras diferentes devem aparecer na descrição
do problema para o problema pertencer a esta categoria. Seguem
W
linhas, cada uma contendo uma palavra-chave dessa categoria.
Todos os nomes possuem menos de 31
caracteres, onde cada
caractere está no intervalo a..z
ou A..Z
.
Por fim, haverá a descrição do problema, com no máximo 1200
linhas,
onde cada linha possui menos de 101
caracteres e não há palavras
que começam em uma linha e terminam na outra. A igualdade entre duas palaras
é case sensitive. O fim da descrição de um problema é indicada por uma
linha em branco.
Saída
Para cada conjunto de entrada, você deve imprimir uma linha indicando a
categoria do problema. Se o problema pertence a mais de uma categoria,
você deve imprimir todas elas, na ordem em que aparecem na entrada,
separadas por vírgulas. Se o problema não pertence a nenhuma categoria
você deve imprimir "SQF Problem"
, sem as aspas.
Exemplo
Entrada: 1 2 Graph 4 3 node edge directed distance Geometrical 4 2 point convex polygon boring This is neither a SQF problem nor a graph problem. This is a boring geometrical problem. In this problem you should calculate the convex area of a regular polygon. Saída: Geometrical
Autores do Problema: Sebastião Alves e Sérgio Queiroz de Medeiros
Adicionado por: | Wanderley Guimarăes |
Data: | 2007-09-28 |
Tempo limite: | 0.100s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL |
Origem: | Primeira Seletiva para Maratona de Programacao UFRN - 2004 |
hide comments
2011-11-02 22:18:03 Douglas Ferlini Bastos Machado[UNB]
a descriçăo deste problema está muito capiciosa, omite vários detalhes que é necessário verificar, como pontuaçăo, números no texto e outros caracteres diferentes de letras, além do que podem haver palavras repetidas para uma mesma categoria(parece contraditório pois o texto cita que elas săo palavras chave) |
|
2011-11-02 21:42:03 thiagojobson [UERN]
Grande Sebastiăo...foi meu professor. |