This problem is yet unsolved. Various people made improvements to it, including Bill Gates! We offer you to try relaxed version of it. Perhaps some of you get curious and could make further advances one day!
So we have a pile of N pancakes, all of different size. We want them sorted in "non-decreasing" order - i.e. smallest
on top, largest below all others.
We need to sort them using peculiar atomic operation - flipping top-part of the pile, consisting of K pancakes,
where K is anything between 2 and N. It works like this - we insert small spade (or "spatula") below the
K-th pancake, counting from the top - lift this "sub-pile" and, flipping it in the air, land them again (in
reversed order).
The unsolved question is: what's the minimum number of flips F(N) which allows to sort any pile of size N?
On this you can read more in wikipedia.
Our task is simpler. Given certain pile of pancakes in disorder - you are to poropose the sequence of flips which sorts it, not exceeding certain limit.
Problem Statement
Pile of pancakes is represented by list of integer numbers in range 0 .. N-1 - so after sorting every
position holds the number equal to index.
Flip operation is denoted by value K meaning "take K numbers from beginning of list and revert them".
Along with the "pile" we get the limit P on number of flips. It is guaranteed that given pile could be sorted
with that number of flips (or less) - however due to randomness some inputs are easier to solve than others.
So the answer should be a list of no more than P values - describing required flip sequence.
Input gives values for N and P in the first line.
Next line provides a list of pancake sizes.
Answer should give a list of P or less values describing sequence of operations for sorting.
Example:
input:
7 4
0 1 6 5 4 2 3
answer:
7 2 5 7