120 – Pilhas de Panquecas
Conhecimento Geral
Pilhas e Filas são frequentemente consideradas o pão com manteiga das estruturas de dados e
são usadas em arquiteturas, parsers, sistemas operacionais, e simulação de eventos discretos.
Pilhas também são importantes na teoria de linguagens formais.
Este problema envolve ambos: manteiga e sustento na forma de panquecas (ao invés do pão) e
um servidor enjoado que vira panquecas de acordo com um único, porém complexo, conjunto de
regras.
O Problema
Dada uma pilha de panquecas, você deverá escrever um programa que indica como a pilha pode
ser ordenada de forma que a panqueca maior fique no final (base) da pilha e a panqueca menor
no topo da pilha. O tamanho da panqueca é dado pelo diâmetro da panqueca. Todas as
panquecas na pilha tem tamanhos diferentes.
A ordenação das panquecas é feita por uma sequência de “viradas”. Uma virada consiste em
inserir a espátula entre duas panquecas e então “virar” (inverter) as panquecas da posição da
espátula até o topo da pilha (invertendo essa subpilha). Uma virada é especificada pela posição
da panqueca na base da subpilha que será virada (posição relativa em relação a toda a pilha). A
panqueca na base da pilha inteira tem a posição 1 e a panqueca no topo da pilha de n panquecas
tem a posição n.
Um pilha é especificada dando-se o diâmetro de cada panqueca na pilha na ordem em que as
panquecas aparecem.
Por exemplo, considere as três pilhas de panquecas abaixo (nas quais a panqueca 8 é a do topo
da pilha da esquerda).
8
4
6
7
5
2
7
6
4
8
5
2
2
5
8
4
6
7
A pilha da esquerda pode ser transformada na pilha do meio através de uma virada(3). A pilha
do meio pode ser transformada na pilha da direita via virada(1).
A Entrada
A entrada consiste de uma sequência de pilhas de panquecas. Cada pilha conterá de 1 a 30
panquecas e cada panqueca terá um diâmetro inteiro entre 1 e 100. A entrada terminará com um
fim_de_linha. Cada pilha é dada como um linha simples com a panqueca do topo aparecendo
como primeira na linha, a panqueca da base aparecerá por última, e todas as panquecas serão
separadas por um espaço em branco. O primeiro elemento de cada linha será o topo da pilha de
panquecas e o último será a base.
A Saída
Para cada pilha de panquecas, a saída deverá imprimir a pilha original em uma linha, seguida
por alguma sequência de viradas que resultará na pilha de panquecas sendo ordenada de forma
que o maior diâmetro estará na base da pilha e o menor no topo. Para cada pilha a sequência de
viradas deve terminar com um 0 (indicando que não são necessárias mais viradas). Uma vez que
a pilha esteja ordenada, nenhuma outra virada precisa ser feita.
Exemplo de Entrada
1 2 3 4 5
5 4 3 2 1
5 1 2 3 4
Exemplo de Saída
1
0
5
1
5
1
2 3 4 5
4 3 2 1
0
1 2 3 4
2 0