Hatena::Grouptopcoder

skyaozoraの日記

 | 

2015-01-07AOJ1197 サイコロ職人

去年の国内予選で引退に追い込まれた憎き問題。

最初vectorで書いてたらTLE喰らった。やっぱりvectorの代入って重いんだな・・・。

//ICPC国内予選14F サイコロ職人(AOJ1197)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
string inf="impossible";
int t[6],u[6],w[6];
bool ok(void){
	rep(i,6){
		if(u[i]<0) return false;
	}
	int a=u[0]+u[5],b=u[1]+u[3],c=u[2]+u[4];
	if(a>b+c || b>a+c+1 || c>a+b+1) return false;
	return true;
}
string cal(int a,int b){
	rep(j,6) u[j]=w[j];
	if(!ok()) return inf;
	int d,n=0;rep(i,6) n+=w[i];
	string ret="";
	rep(i,n){
		//E
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[1];u[1]=u[5];u[5]=u[3];u[3]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='E';continue;}
		//N
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[2];u[2]=u[5];u[5]=u[4];u[4]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='N';continue;}
		//S
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[4];u[4]=u[5];u[5]=u[2];u[2]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='S';continue;}
		//W
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[3];u[3]=u[5];u[5]=u[1];u[1]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='W';continue;}
	}
	return ret;
}
int main()
{
	int a,b;
	while(cin>>t[0]>>t[1]>>t[2]>>t[3]>>t[4]>>t[5],t[0]+t[1]+t[2]+t[3]+t[4]+t[5]){
		sort(t,t+6);
		string ret=inf;
		cin>>a>>b;a--;
		while(1){
			rep(j,6) w[j]=t[j];
			string s=cal(a,b);
			if(ret==inf) ret=s;
			else if(ret>s) ret=s;
			if(!next_permutation(t,t+6)) break;
		}
		if(ret==inf) cout<<ret<<endl;
		else cout<<ret.substr(a,b-a)<<endl;
	}
}

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/skyaozora/20150107
 |