1997 Woburn Computer Programming Challenge

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.

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 in 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:

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 Specification

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 Specification

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.
You will be scored (out of a maximum of $10$ points) based on the number of flips the submission uses, calculated using the following formula: $10\times \frac{1}{m}\sum _{i=1}^m{\left(\frac{\text{No. of flips used by the reference solution for case }i}{\text{No. of flips printed by the user for case }i}\right)}^2$. Furthermore, if the user prints more than $2N-2$ flips excluding the final $0$ for any of the $m$ cases, no points are awarded and the WA verdict is given.

Sample Input

3
5
1 3 5 6 12
5
5 4 3 2 1
5
5 1 2 3 4

Sample Output

0
1 0
1 2 0