SRM 507 Medium CubePacking

問題概要

Ns個の1x1x1の立方体およびNb個のLxLxLの立方体がある。
これらを直方体に、立方体の辺が直方体の辺に平行になるようにつめる。
(すきまがあっても良い)


このとき、全ての立方体を詰められる直方体のうち、最小のものの体積を求めよ。

制約条件

Ns≦10^9,
Nb≦10^6,
L≦10

答えはintに収まることが保証されている。

方針

下の日記で書いた、


直方体の体積Vを(Ns+Nb*L^3以上で)決める>
その体積をもつ直方体にLxLxLの立方体が全部入る
という判定問題にはできる。


最悪でも一列に積み上げる場合で抑えられるので、調べるVはNs+Nb*L^3+100までに抑えられる。


だけど体積決めたときに直方体を全列挙なんて出来るだろうか。
Vは20億くらい。a≦b≦cとして、(20億)^(1/3) * (20億)^(1/2) * 100通りくらい調べないとだめ。


これが実は間に合うらしいorz

bool ok(int x,int y,int z,int nb,int l){
	int cnt=(x/l)*(y/l)*(z/l);
	return cnt>=nb;
}
bool ck(int V,int nb,int l,int a){
	for(int b=1;b*b<=V/a;b++)
	if(V/a%b==0&&ok(a,b,V/a/b,nb,l))return 1;
		return 0;
}
class CubePacking {
	public:
	int getMinimumVolume(int Ns, int Nb, int L) 
	{
		int V=Ns + Nb*L*L*L;
		for(;;V++){
			for(int x=1;x*x<=V;x++)if(V%x==0){
				if(ck(V,Nb,L,x)||ck(V,Nb,L,V/x))return V;
			}
		}
	}
};