首页 > 代码库 > zoj zju 2991 Flipping Burned Pancakes

zoj zju 2991 Flipping Burned Pancakes

2024-11-21 00:17:02   202人阅读

Flipping Burned Pancakes
Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge
The cook at the Frobbozz Magic Pancake House sometimes falls asleep on the job while cooking pancakes. As a result, one side of a stack of pancakes is often burned. Clearly, it is bad business to serve visibly burned pancakes to the patrons. Before serving, the waitress will arrange the stacks of pancakes so that the burned sides are facing down. You must write a program to aid the waitress in stacking the pancakes correctly.


We start with a stack of N pancakes of distinct sizes, each of which is burned on one side. The problem is to convert the stack to one in which the pancakes are in size order with the smallest on the top and the largest on the bottom and burned side down for each pancake. To do this, we are allowed to flip the top k pancakes over as a unit (so the k-th pancake is now on top and the pancake previously on top is now in the k-th position and the burned side goes from top to bottom and vice versa).


For example (+ indicates burned bottom, - a burned top):


+1 -3 -2 [flip 2] -> +3 -1 -2 [flip 1] -> -3 -1 -2 [flip 3] -> +2 +1 +3 [flip 1] -> -2 +1 +3 [flip 2] -> -1 +2 +3 [flip 1] -> +1 +2 +3 You must write a program which finds a sequence of at most (3n - 2) flips, which converts a given stack of pancakes to a sorted stack with burned sides down.


Input


The first line of the input contains a single decimal integer, N, the number of problem instances to follow. Each of the following N lines gives a separate dataset as a sequence of numbers separated by spaces. The first number on each line gives the number, M, of pancakes in the data set. The remainder of the data set is the numbers 1 through M in some order, each with a plus or minus sign, giving the initial pancake stack. The numbers indicate the relative sizes of the pancakes and the signs indicate whether the burned side is up (-) or down (+). M will be, at most, 30.


Output


For each dataset, you should generate one line of output with the following values: The dataset number as a decimal integer (start counting at one), a space, the number of flips (K, where K >= 0) required to sort the pancakes and a sequence of K numbers, each of which gives the number of pancakes to flip on the corresponding sorting step. There may be several correct solutions for some datasets. For instance 3 2 3 is also a solution to the first problem below.


Sample Input


3
3 +1 -3 -2
4 -3 +1 -2 -4
5 +1 +2 +3 +4 -5


Sample Output


1 6 2 1 3 1 2 1
2 6 4 1 4 3 1 2

3 3 5 1 5


题意： 输入第一个数n 表示案例数。每行开头的m表示一共有多少的饼。他们尺寸是不一样的，大小分别是1-m。然后+表示朝上，-表示朝下。而且前面输入的饼是在后面的饼的上面。像第一个案例 3 +1 -3 -2  。1号饼在最上面，2号饼在最下面。而且2和3都是反着的。现在需要通过不停的反转饼来使饼都朝上，而且最顶上的饼最小，向下饼的大小层层增大。第一个案例，要让最后饼的摆放是 +1 +2 +3，就表示完成了。每次操作都是把第一个饼开始至任意一个饼，这段区间里的饼全部一起反转过来。最后输出的第一个数是案例数，第二个数表示操作数，接下来的数全是表示操作。如第一个案例的输出1 6 2 1 3 1 2 1，表示有6个操作。第一次操作是2，就是把1-2的饼翻过来，结果是3 -1 -2。

因为是特判，没有操作数限制，所以可以直接从底下往上模拟来做。把最底下放好最好的之后，再一层一层向上，慢慢完成。



#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;

int code[50];
int shang[50];
int make[99999];

void reserve(int n)
{
	for(int i=1;i<=(1+n)/2;i++)
	{
		int t;
		t=code[i];
		code[i]=code[n-i+1];
		code[n-i+1]=t;
		swap(shang[i],shang[n-i+1]);
	}
	for(int i=1;i<=n;i++)
		shang[i]^=1;
}
int main()
{
	int t;  
	int cas=1; 
	int n;
	int op;
	scanf("%d",&t);

	while(t--)
	{
		scanf("%d",&n);
		op=0;
		for(int i=1;i<=n;i++)
		{
			char ch;
			scanf(" %c%d",&ch,&code[i]);
			if(ch=='+')
				shang[i]=1;
			else 
				shang[i]=0;
		}
		for(int i=n;i>=1;i--)//修复第i个饼  从底层开始   i饼标号
		{
			for(int j=1;j<=n;j++)//从每个位置找i这个饼  j表示位置  code【j】表示标号
			{
				if(i==code[j])//找到i这个饼
				{
					if(i==j&&shang[j])//如果是最后要求的位子而且是朝上的
						break;
					else if(i==j&&shang[j]==0)//要求的位子 朝下
					{
						if(j==1)
						{
							make[op++]=j;
							reserve(j);
							break;
						}
						make[op++]=j;
						make[op++]=1;
						make[op++]=j;
						reserve(j);
						reserve(1);
						reserve(j);
					}
					else if(shang[j])//不在要求的位子 朝上
					{
						make[op++]=j; 
						make[op++]=i;
						reserve(j);
						reserve(i);
					}
					else//朝下
					{
						if(j==1)
						{
							make[op++]=i;
							reserve(i);
							break;
						}
						make[op++]=j;
						make[op++]=1;
						make[op++]=i;
						reserve(j);
						reserve(1);
						reserve(i);
					}

					break;
				}
			}
		}
		printf("%d %d",cas++,op);
		for(int i=0;i<op;i++)
		{
			printf(" %d",make[i]);
		}
		puts("");
	}

	return 0;
}


zoj zju 2991 Flipping Burned Pancakes


联系
我们