flapjacks.cpp
[Problem Description]
Baking a perfect bunch of pancakes on a shelf is a highly skilled job, because no matter how hard you work, the diameter of the pancakes will vary. In order to be neat, you can sort all the cakes by size so that the diameter of all the cakes under each cake is larger than it.
Sorting the cake is achieved through a series of flip operations. There is a shovel that can be inserted between the two cakes and turned over all the cakes on top of the shovel. Each rollover operation is described by the position of the bottom rolled cake in the whole pile. If there are n cakes, the bottom cakes are 1 and the top cakes are n.
A pile of pancakes is represented by the diameters of the pancakes from top to bottom. For example, in the bottom three piles of cakes, the top one has a diameter of 8:
8 7 2
4 6 5
6 4 8
7 8 4
5 5 6
2 2 7
The left-most pile can be transformed into the middle pile by operating flip(3) and the right pile by operating flip(1).
[Input Format]
The input contains data from several cakes. The number of sheets per pile is between 1 and 30, and the diameter of each cake is an integer between 1 and 100. The input terminates with a file terminator. The data for each pile is given in a separate line. The first number in each row represents the diameter of the top cake, and the last number represents the diameter of the bottom cake. Two adjacent numbers are separated by a space.
[Output Format]
For each pile of cake, your program first outputs the original sequence in a single line, and then in the next line it outputs a sequence of flip operations that will allow the largest cake to be at the bottom and the smallest cake to be at the top. The flip sequence should end at 0, indicating that no additional flips are necessary. When a bunch of cakes is arranged, don't make any extra moves.
[Time limit, space requirement]
One second, 256M.
[Input and Output Samples]
flapjacks .in
flapjacks .out
1 2 3 4 5
5 4 3 2 1
5 1 2 3 4
1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0

//  
// The data is sorted first, and then the original sequence is transformed into the final sequence according to the sorted results. In sorting, because there may be  
// The two cakes have the same diameter, so the serial number of the data needs to be recorded. The method of recovery is to find the X that has not been sorted currently, and turn it over to the top first.  
// Then flip to its position after the final sorting.  
      
#include <iostream>  
#include <sstream>  
#include <algorithm>  
#include <cstdio> 
      
using namespace std;  
      
#define MAXSIZE 30  
      
struct pancake  
{  
    int diameter;  
    int index;  
};  
      
pancake pancakes[MAXSIZE];  
pancake original[MAXSIZE];  
      
bool cmp(pancake x, pancake y)  
{  
    return x.diameter < y.diameter;  
}  
      
void flip(int pos, int size)  
{  
    pancake tmp;  
    int i = 0, j = size - pos;  
    for (; i < j; i++, j--)  
        if (original[i].diameter != original[j].diameter)  
        {  
            tmp = original[i];  
            original[i] = original[j];  
            original[j] = tmp;  
        }  
}  
      
int main()  
{  
    
	string line;  
	freopen("flapjacks.in","r",stdin);
	freopen("flapjacks.out","w",stdout);
    while (getline(cin, line))  
    {  
        // Echo.  
        cout << line << endl;  
      
        // Read in the data.  
        int capacity = 0;  
        istringstream iss(line);  
        while (iss >> pancakes[capacity].diameter)  
        {  
            pancakes[capacity].index = capacity;  
            original[capacity] = pancakes[capacity];  
            capacity++;  
        }  
      
        // Sort.  
        sort(pancakes, pancakes + capacity, cmp);  
      
        // Perform a flip operation. If the largest element i is not in the first place, the serial number is found first, and then  
        // Turn it over to the top first, then to position i.  
        for (int i = capacity - 1; i >= 0; i--)  
        {  
            // Find this element in the current sequence.  
            // If the original serial number is different from the current one, it needs to be reversed.  
            int marker;  
            for (int j = 0; j < capacity; j++)  
                if (original[j].index == pancakes[i].index)  
                {  
                    marker = j;  
                    break;  
                }  
      
            if (marker != i)  
            {  
                if (marker != 0)  
                {  
                    cout << (capacity - marker) << " ";  
                    flip(capacity - marker, capacity);  
                }  
  
                cout << (capacity - i) << " ";  
                flip(capacity - i, capacity);  
            }  
        }  
      
        cout << "0" << endl;  
    }  
    
	fclose(stdin);
	fclose(stdout);  
    return 0;  
}