読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

2012 WUPC2 : D - 5キューブ

その他コンテスト

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

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

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

  • 1辺5の立方体はそれだけで器を占拠するので、立方体1個当たり器を1個使う
  • 1辺4の立方体は器に1個しか入らないので、立方体1個当たり器を1個使う。このとき、隙間に器あたり1辺1の立方体が5^3-4^3=61個入る。
  • 1辺3の立方体は器に1個しか入らないので、立方体1個当たり器を1個使う。このとき、隙間に器あたり1辺2の立方体が7個入る。まだ隙間があれば、1辺1の立方体で埋める。
  • 1辺2の立方体は器に8個までしか入らないので、立方体8個当たり器を1個使う。このとき、隙間があれば、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;
}

まとめ

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

広告を非表示にする