SRM507 Div1 Medium

500

2辺の長さを決める。よくあるアレ。

入力が大きいので、とりあえず2辺を決める方向で考える。
大きい方に合わせて残りの1辺の長さを決めて、小さい方で帳尻を合わせてみる。
問題は、小さい方をキューブのどの面の方向に並べるか。

i <= j <= k のとき、
A. (i + 1) * j * k
B. i * (j + 1) * k
C. i * j * (k + 1)

格方向へ1だけ大きくした場合、 i * j だけ増加する C が小さそう。

大きくする量が 1 より大きくても同じ事が言えそうな気がする。
小さい方の残りは、ある1つの面だけを必要なだけ伸ばして対処してみる。
サンプル合う。投げる。通る。

class CubePacking {
public:
  int getMinimumVolume(int Ns, int Nb, int L)
  {
    const lli U = INT_MAX;
    lli mn = U;
    for (lli i = 1; (i * i <= double(U) / i); ++i) {
      for (lli j = 1; (j * j <= double(U) / i); ++j) {
        lli k;

        lli a = i / L;
        lli b = j / L;
        lli B = a * b;
        if (B <= 0) continue;

        k = ((Nb / B) + (bool)(Nb % B)) * L;
        lli c = k / L;

        lli d = (a * b * c) - Nb;
        if (d < 0) continue;

        lli rest = Ns - ((i * j * k) - (L * L * L) * Nb);
        if (0 < rest) {
          lli e = i * j;
          k += (rest / e) + (bool)(rest % e);
        }
        mn = min(mn, i * j * k);
      }
    }
    return mn;
  }
};