SPOJ Problem Set (seletivas)
1823. Problemas SQF
Problema: PSQF
|
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: | 1s
|
| Tamanho do fonte: | 50000B |
| Linguagem permitida: | Todas exceto: AWK CLOJ ERL F# GO JS PERL 6 SCALA SED TCL |
| Origem: | Primeira Seletiva para Maratona de Programacao UFRN - 2004 |