INPUT FILE: prob3.in
OUTPUT FILE: prob3.out
Background
Stacks and queues are often considered the bread and butter of data structures
and find use in architecture, parsing, operating systems, and discrete event
simulation. Stacks are also important in the theory of formal languages. This
problem involves both butter and sustenance in the form of pancakes rather than
bread in addition to a finicky server who flips pancakes according to a unique,
but complete set of rules.
The Problem
Given a stack of pancakes, you are to write a program that indicates how the
stack can be sorted so that the largest pancake is on the bottom and the smallest
pancake is on the top. The size of a pancake is given by the pancake's diameter.
All pancakes is a stack have different diameters. Sorting a stack is done by
a sequence of pancake "flips". A flip consists of inserting a spatula
between two pancakes in a stack and flipping all of the pancakes on top of the
spatula (reversing the sub-stack). A flip is specified by giving the position
of the pancake on the bottom of the sub-stack to be flipped (relative to the
whole stack). The pancake on the bottom of the sub-stack thus becomes the top
of the sub-stack (and the top of the whole stack) and vice-versa. The bottom
pancake has position 1 and the top pancake of a stack of n pancakes has position
n.
For example, consider the three stacks of pancakes below:
|
8 |
7 6 4 8 5 2 |
2 5 8 4 6 7 |
The stack on the left can be transformed into the stack in the middle via flip(3). The middle stack can be transformed into the right stack via the command flip(1).
[Does this problem get any harder if the orientation of each pancake must be preserved in the end? - Dave]
INPUT
The first line of the input is m, indicating the number of test-cases to
consider.
The first line of each test case is n, the number of pancakes in the stack.
The second line of each test case contains the diameters of the n pancakes in
the stack, from top to bottom.
Each stack will have between 1 and 30 pancakes and each pancake will have an
integer diameter from 1 to 100.
OUTPUT
For each stack of pancakes, output some sequence of flips that brings the stack
into sorted order (largest on the bottom, smallest on top). Each of these sequences
should be terminated by a 0, and appear on a line by itself. The fewer flips
you perform, the more marks you will recieve.
Sample Input File
3 5 1 3 5 6 12 5 5 4 3 2 1 5 5 1 2 3 4
Output for Sample Input
0 1 0 1 2 0