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
2012-07-02 21:48:42 DevCemJava - Girdacio [FATEC-MC]
é verdade, consegui rodar em Java com tempo: 3.01 :(
2011-12-18 15:50:05 Fernando Fonseca [ITA]
Se Python passou esse problema, Java passa!
2011-06-23 13:27:53 LST [UFSCar]
@Marcos, a resposta pode ser obtida em tempo O(1). Na maioria dos problemas a linguagem năo é o fator limitante, e sim o algoritmo utilizado.
2011-04-14 16:46:32 Marcos Lima
O tempo disponível é o principal problema para quem está em Java, săo muitos casos de teste.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.