2012 WUPC2 : D - 5キューブ

SRMでへこんだところで、WUPC2の復習を継続。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_04

１辺の長さが1～5の立方体の数が与えられるので、１辺５の立方体の器が何個あれば全部の立方体を格納できるかを答える。

下記を地道に行って大きい立方体から詰めていく。

• 1辺5の立方体はそれだけで器を占拠するので、立方体１個当たり器を１個使う
• 1辺4の立方体は器に１個しか入らないので、立方体１個当たり器を１個使う。このとき、隙間に器あたり1辺1の立方体が5^3-4^3=61個入る。
• 1辺3の立方体は器に１個しか入らないので、立方体１個当たり器を１個使う。このとき、隙間に器あたり1辺2の立方体が7個入る。まだ隙間があれば、1辺1の立方体で埋める。
• 1辺2の立方体は器に8個までしか入らないので、立方体8個当たり器を１個使う。このとき、隙間があれば、1辺1の立方体で埋める。
• 1辺1の立方体がまだ余ってたら、器あたり125個ずつ詰めていく。

ll N[6];

void solve() {
	ll x,y,i,j,rr,TM;
	ll p,t,c;
	
	FOR(x,5) N[x+1]=GETi();
	
	//L=5
	t=N[5];
	
	//L=4
	t+=N[4];
	N[1]-=61*N[4];
	if(N[1]<0) N[1]=0;
	
	//L=3
	t+=N[3];
	
	c=(125-27)*N[3]; //空き
	p=min(N[2],7*N[3]);
	N[2]-=p;
	c-=8*p;
	
	N[1]-=c;
	if(N[1]<0) N[1]=0;
	
	if(N[2]>0) {
		x=((N[2]+7)/8);
		t+=x;
		c = 125*x - N[2]*8;
		N[1]-=c;
		if(N[1]<0) N[1]=0;
	}
	
	t+=(N[1]+124)/125;
	
	_P("%lld\n",t);
	return;
}

まとめ

面倒だがしっかり手順を踏めばよい問題。
面白い問題だと思ったけど、似たような問題はすでにあったらしいね。