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 pancakes has position .
For example, consider the three stacks of pancakes below:
8 4 6 7 5 2 |
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 Specification
The first line of the input is , indicating the number of test cases to
consider.
The first line of each test case is , the number of pancakes in the
stack.
The second line of each test case contains the diameters of the
pancakes in the stack, from top to bottom.
Each stack will have between and pancakes and each pancake will
have an integer diameter from to .
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 , and appear on a
line by itself.
You will be scored (out of a maximum of points) based on the number of flips the submission uses, calculated using the following formula: . Furthermore, if the user prints more than flips excluding the final for any of the 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
Comments