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

OBIHANOI - Torres de Hanói

O quebra-cabeças Torres de Hanoi é muito antigo e conhecido, sendo constituído de um conjunto de N discos de tamanhos diferentes e três pinos verticais, nos quais os discos podem ser encaixados.

Cada pino pode conter uma pilha com qualquer número de discos, desde que cada disco não seja colocado acima de outro disco de menor tamanho. A configuração inicial consiste de todos os discos no pino 1. O objetivo do quebra-cabeças é mover todos os discos para um dos outros pinos, sempre obedecendo à restrição de não colocar um disco sobre outro menor.

Um algoritmo para resolver este problema é o seguinte.

procedimento Hanoi(N, Orig, Dest, Temp)
   se N = 1 então
      mover o menor disco do pino Orig para o pino Dest;
   senão
      Hanoi(N-1, Orig, Temp, Dest);
      mover o N-ésimo menor disco do pino Orig para o pino Dest;
      Hanoi(N-1, Temp, Dest, Orig);
   fim-se
fim

Tarefa

Sua tarefa é escrever um programa que determine quantos movimentos de trocar um disco de um pino para outro serão executados pelo algoritmo acima para resolver o quebra-cabeça.

Entrada

A entrada possui vários conjuntos de teste. Cada conjunto de teste é composto por uma única linha, que contém um único número inteiro N (0 <= N <= 30), indicando o número de discos. O final da entrada é indicado por N = 0.

Saída

Para cada conjunto de teste, o seu programa deve escrever três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado seqüencialmente a partir de 1. A segunda linha deve conter o número de movimentos que são executados pelo algoritmo dado para resolver o problema das Torres de Hanói com N discos. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
1
2
0

Saída
Teste 1
1

Teste 2
3

Restrições

0 <= N <= 30 (N = 0 apenas para indicar o final da entrada)


Adicionado por:Wanderley Guimarăes
Data:2006-05-05
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:Olimpiada Brasileira de Informatica 2003

hide comments
2015-05-29 05:17:22
Fui compilar em pascal com esse 2^n - 1 e dá tempo limite excedido. Alguém pode me dizer o porquê? TEm algum outro jeito de contar os movimentos sem essa fórmula? Valeu
2014-12-19 07:47:03 Gabriel Oliveira Alves [IFSP]
Pessoal, ao invés de imprimir direto na tela "2^n-1", atribuam esse valor a uma variável long long int.
O meu năo funcionou por isso. Se vocę imprimir o resultado direto na tela, sem usar uma long long int, ele imprime em notaçăo científica, mas no gabarito os resultados estăo escritos por completo, e năo em notaçăo científica.

Por exemplo, para n=30, se vocę imprimir direto na tela o valor que sai é:

1.073741823e09, mas o valor esperado pelo corretor é 1073741823.

Acredito que muitos estăo tendo esse problema, entăo fica a dica.
2013-11-25 00:39:50 Washington
1 -> 1
2 -> 3
3 -> 7
4 -> 15
5 -> 31
...
2013-07-15 05:48:05 Eduardo Maia [UECE]
Nicolas

năo sei como está seu código, mas a resposta em si pode estar certa, porém, é algum detalhe que vocę está deixando passar. tenta olhar a tua saída, por exemplo, se o nome "Teste" está com a letra inicial maiúscula, se vocę está deixando de pular uma linha (porque o problema diz que a 3Ş linha deve estar em branco). enfim, já que sua resposta está dando certo, tenta olhar esses mínimos detalhes, que săo suficientes para dar resposta errada.

Last edit: 2013-07-15 05:49:57
2013-05-24 06:05:32 Nicolas Almeida
O meu bate com todos os casos de teste, bate com a própria fórmula das torres de hanoi, mas ainda assim dá worng answer '-'
2013-05-17 21:11:41 Leonardo [IFRN]
ops.. (2^n)-1 movimentos né?

Last edit: 2013-05-17 21:11:59
2013-05-17 21:10:39 Leonardo [IFRN]
2^N movimentos...
2013-05-17 21:10:26 Leonardo [IFRN]
Seria 2^n né?
2013-01-28 23:50:44 Murilo Panosso
como nosso amigo Renan Dias disse... utilizem a álgebra a seu favoor !!
2013-01-03 13:44:19 Renan Dias [FEI]
Pessoal, năo percam tempo implementando esse pseudocódigo, colocando contador e outras coisas mais. Utilizem a álgebra a seu favor que 1 (uma) linha de código é o suficiente para saber quantos movimentos serăo executados!

Last edit: 2013-01-03 13:45:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.