e.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
using namespace std;

int n,l[22],rsize,ans;

struct node
{
	int p,w;
	bool act;
	void operator()(int p_,int w_)
	{
		p=p_;
		w=w_;
		act=true;
		for(int i=1;i<=n;++i)
			if(p_==l[i])act=false;
	}
} r[55];

void read(int& x)
{
	scanf(" ");
	for(x=1;;)
	{
		char c=getchar();
		if(c=='0')x+=x;
		else if(c=='1')x+=x+1;
		else break;
	}
}

void split(int ms)
{
	int maxw=0,b;
	for(int i=1;i<=rsize;++i)if(r[i].act)
		if(r[i].w>maxw)maxw=r[i].w,b=i;
	if(!maxw)
	{
		++ans;
		return;
	}
	if(maxw-1<ms)ms=maxw-1;
	r[b].act=false;
	for(int i=maxw+1>>1;i<=ms;++i)
	{
		r[++rsize](r[b].p<<1,maxw-i);
		r[++rsize](r[b].p<<1^1,i);
		split(maxw-i);
		rsize-=2;
	}
	r[b].act=true;
}

int main()
{
	for(int te=1;scanf("%d",&n),n;++te)
	{
		for(int i=1;i<=n;++i)read(l[i]);
		r[rsize=1](1,100);
		ans=0,split(~0U>>1);
		printf("Case %d: %d\n",te,ans);
	}
	return 0;
}