Next: A entrada Up: No Title Previous: Exemplos

Problema 4: Panquecas

Dada uma pilha de panquecas, voc� deve escrever um programa que indica como a pilha pode ser ordenada de forma que a maior panqueca est� no fundo e a menor panqueca est� no topo. O tamanho de uma panqueca � dado pelo seu di�metro. Todas as panquecas de uma pilha t�m di�metros diferentes.

A ordena��o da pilha � feita atrav�s de uma seq��ncia de ``giros'' ( flips) de panquecas. Um giro consiste em inserir a esp�tula entre duas panquecas em uma pilha e girar (reverter) todas as panquecas que est�o em cima da esp�tula (revertendo a subpilha). Um giro � especificado dando a posi��o da panqueca da subpilha que ser� revertida (em rela��o � pilha completa). A panqueca do fundo da pilha inteira tem posi��o 1 e a panqueca do topo de uma pilha com $n$ panquecas tem posi��o $n$.

Uma pilha � especificada dando o di�metro de cada panqueca da pilha na ordem em que as panquecas aparecem.

Por exemplo, considere as tr�s pilhas de panquecas abaixo (nas quais a panqueca 8 est� no topo da pilha mais � esquerda):

A pilha mais � esquerda pode ser transformada na pilha do meio fazendo a opera��o flip(3). A pilha do meio pode ser transformada na pilha � direita atrav�s do comando flip(1).

• A entrada
• A sa�da
• Exemplo