Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CARDAPIO - Cardápio da Sra Montagny

Sra. Montagny é uma socialite de Quebec, que passa as férias em Banff, na sua mansão à beira do Lake Louise. Seus jantares são famosos porque ela com antecedência passa um questionário aos convidados onde os mesmos participam da escolha do cardápio. No questionário, a famosa magnata lista todos os pratos que poderá fazer no jantar, oferecendo uma coluna para o convidado selecionar o prato e outra para vetá-lo. É permitido fazer apenas duas escolhas no questionário, ou seja, cada convidado pode selecionar um prato e vetar outro, vetar dois pratos ou selecionar dois pratos. A Sra. Montagny garante que todos os convidados terão pelo menos um de seus desejos atendidos.

Antigamente ela mesma dava conta de montar o cardápio e atender o que prometia, mas com o crescimento de suas festas isso tem se tornado impossível. Assim, ela resolveu contratar vocês para fazer um programa que recebe os pedidos dos convidados e responde se é montar um possível cardápio para a festa.

Entrada

A entrada é composta de diversas instâncias. Cada instância começa com um inteiro n (1 <= n <= 1000), indicando a quantidade de questionários recebidos pela Sra. Montagny. Cada uma das próximas n linhas contém dois nomes de comida indicando a preferência de cada convidado. Um nome de comida é uma seqüência de letras [a-z] com no máximo 20 letras. Quando o nome de uma comida é iniciado por "!" significa que o convidado deseja vetar a comida, caso contrário ele deseja selecionar.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte você deve imprimir sim se for possível atender pelo menos um desejo de cada convidado e nao caso contrário.

Após cada instância, seu programa deve imprimir uma linha em branco.

Exemplo

Entrada
2
!feijoada !file
rabada feijoada
4
arroz churrasco
!arroz !churrasco
arroz !churrasco
!arroz churrasco

Saída
Instancia 1
sim

Instancia 2
nao

Adicionado por:Wanderley Guimarăes
Data:2007-08-16
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva para Maratona de Programação do IME - 2007

hide comments
2014-12-16 03:04:30 Leandro de Andrade Moura [UFPE]
Tentem trie.
2014-08-29 02:55:36 Saulo
Em Java nao da para saber como termina a entrada de dados por isso sempre retorna "tempo limite excedido"
2014-08-13 10:36:08 ben crazy


Last edit: 2014-08-13 10:36:30
2013-12-24 09:25:50 Altamir Gomes Bispo Junior [UFSCar]
Passou em 0,83s com Java!

Last edit: 2013-12-24 17:29:36
2013-08-27 23:35:01 Tiago Reis [UFSCar]
O tempo limite desse problema é muito apertado. Podiam aumentar isso, porque é muito frustrante vocę usar um algoritmo correto e eficiente e tomar TLE por năo ter escovado bits suficientes.
2013-03-25 13:38:47 Edson Silva CCM [UFABC]
:[
Tomando uma surra de TLE sem saber porque. Alguém sabe me informar se existe diferença entre:
['printf' imediado para cada instância]
<X>
[aguardar EOF para "printar" cada instancia] ?????

Last edit: 2013-03-25 13:41:35
2013-03-05 18:58:46 João Paulo Bologna
Assim como o Fernando disse, a entrada termina com EOF.

Last edit: 2013-03-05 19:00:42
2012-03-30 20:01:12 Natan Pedrosa [UESPI]
como cria a condiçăo EOF em java

Last edit: 2012-03-30 20:01:35
2011-10-06 03:29:51 Fernando Fonseca [ITA]
O meu programa passou, entăo podem presumir que a entrada termina com EOF (fim de arquivo).
2011-09-03 15:52:28 Jorge Gabriel [UNIFEI]
duvida quanto a condiçăo de parada...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.