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; } } } };