Login Registre-se

Você pode ganhar um iPad 2 na promoção do Javafree

O Portal javafree.org inicia mais uma promoção para os usuários do fórum. Quem publicar mais posts válidos (perguntas ou respostas) entre 16/4 a 13/7 levará para casa um iPad 2 de 16GB!

Clique aqui e saiba mais.
Home > Artigos > Algoritmos e Técnicas de Programação >

[Desafio] Braço Robótico

Publicado por sekkuar em 07/01/2012 - 3.813 visualizações


comentários: 12

Várias áreas da ciência da computação usam domínios simples e abstratos para
estudos analíticos e empíricos. Por exemplo, algumas das primeiras pesquisas de inteligência
artificial nas áreas de planejamento e robótica usavam o mundo dos blocos, no qual um braço
de robô realizava tarefas envolvendo a manipulação de blocos.

O problema consiste em analisar uma série de comandos que instruem um braço de
robô em como manipular os blocos que estão sobre uma mesa. Inicialmente, existem N
( 1< N < 25 ) blocos sobre a mesa (numerados de 0 a N-1), como mostra a figura a seguir.

0

O problema começa com cada bloco na sua posição inicial sobre a mesa e, depois de
uma série de comandos válidos, deve terminar em uma configuração final. Na figura a seguir
é apresentado um exemplo para 6 blocos ( N = 6 ), sendo (a) a configuração inicial e (b) a
configuração final.

0

Entrada



A entrada é composta de apenas um caso de teste. Cada caso de teste é composto de um número indeterminado de linhas.
A primeira linha da entrada contém apenas um numero inteiro N, representando o numero inicial de blocos.
As linhas seguintes contém cada uma um comando, que deve ser executado nas pilhas atuais de blocos.
Os comandos possíveis são:
(Usa-se A para indicar o bloco em movimento e B como bloco de referência.)

* mover A acima B : move o bloco A diretamente acima do bloco B retornando eventuais
blocos que já estiverem sobre A ou B para as suas posições originais.

* mover A topo B : coloca o bloco A no topo da pilha onde está o bloco B
retornando eventuais blocos que já estiverem sobre A para as suas posições originais.

* empilhar A acima B : coloca o bloco A juntamente com todos os blocos que
estiverem sobre ele em cima do bloco B, retornando eventuais blocos que já
estiverem sobre B as suas posições originais.

* empilhar A topo B : coloca o bloco A juntamente com todos os blocos que
estiverem sobre ele no topo da pilha onde está o bloco B.

* encontrar maior : encontra o bloco de maior número da pilha mais alta e o devolve para a
posição inicial (Caso existam duas ou mais pilhas com o mesmo numero de blocos, deve retornar
o maior bloco da pilha de menor valor. Por exemplo, se as pilhas 2 e 5 têm ambas 3 blocos cada,
deve retornar o maior bloco da pilha 2).

* sair : Indica o final da entrada.


Comandos com valores inválidos devem ser ignorados, não alterando as posições dos blocos.

Um comando é inválido quando:

* A é igual a B
* A e B estão na mesma pilha
* A,B < 0
* A,B >= N


Saída


A saída deve ser composta de N linhas, que representam a configuração final do seu Mundo dos Blocos.
Em cada linha deve aparecer o número da pilha seguida de dois pontos
(:). Se existir pelo menos um bloco naquela posição, os dois pontos devem ser
seguidos pela lista de blocos que aparecem naquela pilha separados por um espaço
em branco.

Exemplo 1



Exemplo 2



Exemplo 3






Download:  imagem1.PNG
Size:  2 KB

Download:  imagem2.PNG
Size:  6 KB

comentários: 12