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.|

OBIDOMIN - Dominó

Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em seqüência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo desta tarefa é determinar se é possível colocar todas as peças de um conjunto dado em uma formação válida.

Tarefa

É dado um conjuto de peças de dominó. Cada peça tem dois valores X e Y, com X e Y variando de 0 a 6 (X pode ser igual a Y). Sua tarefa é escrever um programa que determine se é possível organizar todas as peças recebidas em seqüência, obedecendo as regras do jogo de dominó.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de testes contém um número inteiro N que indica a quantidade de peças do conjunto. As N linhas seguintes contêm, cada uma, a descrição de uma peça. Uma peça é descrita por dois inteiros X e Y (0 ≤ X ≤ 6 e 0 ≤ Y ≤ 6) que representam os valores de cada lado da peça. O final da entrada é indicado por N = 0.

Exemplo de Entrada
3
0 1
2 1
2 1
2
1 1
0 0
6
3 0
0 0
1 6
4 1
0 6
2 3
0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter a expressão "sim" se for possível organizar todas as peças em uma formação válida ou a expressão "nao" (note a ausência de acento) caso contrário. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída
Teste 1
sim

Teste 2
nao

Teste 3
sim

(esta saída corresponde ao exemplo de entrada acima)

Restrições

0 ≤ N ≤ 100 (N = 0 apenas para indicar o final da entrada)


Adicionado por:Wanderley Guimarăes
Data:2007-02-24
Tempo limite:0.137s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Origem:Olimpiada Brasileira de Informatica 2001

hide comments
2016-04-06 22:46:06 Elsio [UFABC]
Ué!
Pq não pode C++ 4.3.2 ?????
2014-07-27 05:46:09 Vagner Kaefer [UTFPR]
Dicas: Se for usar grafos lembre que uma busca em profundidade tem que retornar somente uma arvore e cuidado para năo confundir a quantidade de vértices como o limite de numeraçăo de vértices! ;D

O detalhe vai ser conferir um detalhe sobre os graus dos vértices para chegar a resposta correta!

Last edit: 2014-07-27 05:47:06
2014-06-30 20:08:10 Washington
Existe algum algorítmo específico para este tipo de exercício?

Last edit: 2015-05-13 22:38:30
2013-12-25 14:22:04 Tiago Nápoli
Deem uma olhada em Eulerian paths e Eulerian cycles
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.