记录编号	36477	评测结果	AAAAAAAA
题目名称	分球	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.230 s
提交时间	2012-03-13 20:54:44	内存使用	11.69 MiB

#include <fstream>
#include <cstring>
#include <memory.h>
using namespace std;

ifstream input("balls.in");
ofstream output("balls.out");

int sn,n,pn,temp,pos[100001],dad[100001],que[100001][16];
char quech[16];
bool flag,used[3][3][3][3][3][3][3][3][3][3][3][3][3][3];

bool succ(int head)
{
	int i,c;
	c=0;
	for (i=0;i<n;i++)
	{
		if (que[head][i]==1)
			c++;
		else if (que[head][i]==2)
			return(false);
		if (c==sn)
			break;
	}
	return(true);
}

void printans(int pos,int deep)
{
	int i;
	if (pos!=0)
		printans(dad[pos],deep+1);
	else
		temp=deep;
	output<<temp-deep<<' ';
	for (i=0;i<n;i++)
		if (que[pos][i]==0)
			quech[i]=' ';
		else if (que[pos][i]==1)
			quech[i]='a';
		else// if (que[pos][i]==2)
			quech[i]='b';
	output<<quech<<"\n";
}

int main(void)
{
	int i,j,jj,k,l,tail,head,pos1,pos2;
	char ch1,ch2;
	bool flag2;
	input>>k;
	for (i=0;i<k;i++)
	{
		tail=0;
		head=0;
		memset(que,0,sizeof(que));
		memset(dad,0,sizeof(dad));
		memset(pos,0,sizeof(pos));
		memset(used,0,sizeof(used));
		memset(quech,0,sizeof(quech));
		input>>n;
		flag=false;
		sn=n-1;
		n+=n;
		pn=n-1;
		flag2=false;
		for (j=0;j<n;j++)
		{
			input.get(quech[j]);
			while (quech[j]!=' '&&quech[j]!='a'&&quech[j]!='b')
				input.get(quech[j]);
			if (quech[j]==' ')
				que[0][j]=0;
			else if (quech[j]=='a')
				que[0][j]=1;
			else// if (quech[j]=='b')
				que[0][j]=2;
			if (!flag2&&que[0][j]==0)
			{
				pos[0]=j;
				flag2=true;
			}
		}
		used[que[0][0]][que[0][1]][que[0][2]][que[0][3]][que[0][4]][que[0][5]][que[0][6]][que[0][7]][que[0][8]][que[0][9]][que[0][10]][que[0][11]][que[0][12]][que[0][13]]=true;
		if (succ(head))
		{
			printans(head,0);
			flag=true;
		}
		while (!flag&&tail<=head&&head<=99900)
		{
			pos1=pos[tail]-1;
			pos2=pos[tail]+1;
			for (j=0;!flag&&j<pn;j++)
			{
				if (j==pos[tail]||j==pos1||j==pos2)
					continue;
				head++;
				jj=j+1;
				dad[head]=tail;
				pos[head]=j;
				for (l=0;l<n;l++)
					que[head][l]=que[tail][l];
				ch1=que[head][j];
				ch2=que[head][jj];
				que[head][j]=0;
				que[head][jj]=0;
				que[head][pos[tail]]=ch1;
				que[head][pos[tail]+1]=ch2;
				if (succ(head))
				{
					printans(head,0);
					flag=true;
				}
				if (used[que[head][0]][que[head][1]][que[head][2]][que[head][3]][que[head][4]][que[head][5]][que[head][6]][que[head][7]][que[head][8]][que[head][9]][que[head][10]][que[head][11]][que[head][12]][que[head][13]])
					head--;
				else
					used[que[head][0]][que[head][1]][que[head][2]][que[head][3]][que[head][4]][que[head][5]][que[head][6]][que[head][7]][que[head][8]][que[head][9]][que[head][10]][que[head][11]][que[head][12]][que[head][13]]=true;
			}
			tail++;
		}
		if (!flag)
			output<<"NO SOLUTION\n";
		if (i!=k-1)
			output<<"\n";
	}
	return(0);
}