SRM 507 Div1 medium CubePacking

問題概要

Ns個の1辺1の立方体と
Nb個の1辺Lの立方体
Ns will be between 1 and 1,000,000,000, inclusive.
Nb will be between 1 and 1,000,000, inclusive.
L will be between 2 and 10, inclusive.
がある。
できるだけ小さい直方体に詰めたい。
その長方形の大きさを最小化せよ。

解法

全探索。
2000000000^(1/3) * 2000000000^(1/2)くらい.
総体積+L * L * L よりは絶対に大きくならないことがポイント。
それは、2辺をLにしたとき、必ずそれ以下になるため。

ソース

class CubePacking {
public:
  int getMinimumVolume(lli Ns, lli Nb, lli L) {
    lli V = Nb * L * L * L + Ns;
    lli ans = V + L * L * L ;
    for(lli h = L; h * h * h <= V + L * L * L; h++){
      for(lli w = h; h * w * w <= V + L * L * L; w++){
        lli n = (h / L) * (w/ L);
        lli remain = h * w - n * L * L; 
        lli length = (Nb / n) * L;
        remain = Ns - remain * length;
        if(Nb % n != 0){
          length+= L;
          remain -= (h * w * L - (Nb%n) * L * L * L ) ;
        }
        if(remain > 0){
          length += remain / (h * w);
          if(remain % ( h * w) != 0){
            length++;
          }
        }
        ans = min(ans, h * w * length);
      }
    }
    return ans;
  }
};