UVa 120

From Algorithmist
Jump to: navigation, search

120 - Stacks of Flapjacks[edit]

Summary[edit]

Using only the flipping method explained in the problem statement, sort a stack of pancakes so that they are in order of decreasing diameter from the bottom.

Explanation[edit]

You don't need to find the optimal way of sorting the pancakes, so there can be many approaches to solving this problem, but this method in particular is easy to explain:

Consider any unsorted stack of pancakes of height n. If the largest pancake in that stack is not at the bottom, then it must eventually be moved to the bottom, and this takes at most two flips. The first flip is from the largest pancake, which brings it to the top of the stack. The second flip is from the bottom of the stack, which brings the largest pancake from the top of the stack to the bottom, where it needs to be. Then, this process can be repeated with the n-1 top pancakes of the stack.

Gotcha's[edit]

  • Be sure to stop flipping when the stack is finally sorted!

Input[edit]

1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

Output[edit]

1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0

Solution[edit]