记录编号	35404	评测结果	AAAAAAAA
题目名称	分球	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.672 s
提交时间	2012-02-21 15:42:02	内存使用	0.27 MiB

#include <fstream>
#include <cmath>
#include <set>

#define I_F "balls.in"
#define O_F "balls.out"

const short Maxn=7*2;
const short Maxstep=100;

std::ifstream fin(I_F);
std::ofstream fout(O_F);

struct lb
{
	long s;
	short d, x;
	lb *prep, *succ;
};

short n;
short s[Maxn];
short ansn;
long ans[Maxstep];
bool flag;

void Input();
bool Ok(long);
void Exchange(short*, long&, const bool);
void Delete(lb*);
bool Search();
void Output();

int main()
{
	short m;
	fin>>m;
	for (short i=0; i<m; i++)
	{
		Input();
		flag=Search();
		Output();
	}
	fin.close();
	fout.close();
}

void Input()
{
	fin>>n;
	char t=fin.get();
	while (t!=' ' && (t<'a' || t>'z'))
		t=fin.get();
	for (short i=0; i<n*2; i++)
	{
		if (t=='a')
			s[i]=1;
		else if (t=='b')
			s[i]=2;
		else
			s[i]=0;
		t=fin.get();
	}
}

bool Ok(long x)
{
	short s[Maxn];
	Exchange(s,x,false);
	short j=0;
	for (short i=0; j<n-1; i++)
		if (s[i]==1)
			j++;
		else if (s[i]==2)
			return false;
	return true;
}

void Exchange(short *s, long &x, const bool f)
{
	if (f)
	{
		x=0;
		for (short i=0; i<n*2; i++)
			x+=s[i]*pow(3.0,(double)i);
	}
	else
	{
		long t=x;
		for (short i=0; i<n*2; i++)
		{
			s[i]=t%3;
			t/=3;
		}
	}
}

void Delete(lb *x)
{
	if (x->succ!=NULL)
		Delete(x->succ);
	delete x;
}

bool Search()
{
	lb *head, *tail;
	head=new lb;
	Exchange(s,head->s,true);
	if (Ok(head->s))
	{
		ansn=0;
		ans[0]=head->s;
		delete head;
		return true;
	}
	std::set<long> f;
	head->prep=head->succ=NULL;
	head->d=0;
	for (head->x=0; s[head->x]>0; head->x++);
	tail=head;
	short ts1[Maxn], ts2[Maxn];
	long tx2;
	
	for (lb *temp=head; temp!=NULL; temp=temp->succ)
	{
		Exchange(ts1,temp->s,false);
		for (short i=0; i<n*2-1; i++)
			if (ts1[i]*ts1[i+1]>0)
			{
				for (short k=0; k<n*2; k++)
					ts2[k]=ts1[k];
				ts2[temp->x]=ts1[i], ts2[temp->x+1]=ts1[i+1];
				ts2[i]=ts2[i+1]=0;
				Exchange(ts2,tx2,true);
				if (f.find(tx2)==f.end())
				{
					f.insert(tx2);
					tail->succ=new lb;
					tail=tail->succ;
					tail->prep=temp;
					tail->succ=NULL;
					tail->s=tx2;
					tail->d=temp->d+1;
					tail->x=i;
				
					if (Ok(tail->s))
					{
						ansn=tail->d;
						for (lb *j=tail; j!=NULL; j=j->prep)
							ans[j->d]=j->s;
						Delete(head);
						return true;
					}
					if (tail->d>Maxstep)
					{
						Delete(head);
						return false;
					}
				}
			}
	}
	Delete(head);
	return false;
}

void Output()
{
	using std::endl;
	short t[Maxn];
	if (flag)
		for (short i=0; i<=ansn; i++)
		{
			fout<<i<<' ';
			Exchange(t,ans[i],false);
			for (short j=0; j<n*2; j++)
				if (t[j]==1)
					fout<<'a';
				else if (t[j]==2)
					fout<<'b';
				else
					fout<<' ';
			fout<<endl;
		}
	else
		fout<<"NO SOLUTION\n";
	fout<<endl;
}