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つの面だけを必要なだけ伸ばして対処してみる。
サンプル合う。投げる。通る。

view plainprint?

1. class CubePacking {  
2. public:  
3.   int getMinimumVolume(int Ns, int Nb, int L)  
4.   {  
5.     const lli U = INT_MAX;  
6.     lli mn = U;  
7.     for (lli i = 1; (i * i <= double(U) / i); ++i) {  
8.       for (lli j = 1; (j * j <= double(U) / i); ++j) {  
9.         lli k;  
10.   
11.         lli a = i / L;  
12.         lli b = j / L;  
13.         lli B = a * b;  
14.         if (B <= 0) continue;  
15.   
16.         k = ((Nb / B) + (bool)(Nb % B)) * L;  
17.         lli c = k / L;  
18.   
19.         lli d = (a * b * c) - Nb;  
20.         if (d < 0) continue;  
21.   
22.         lli rest = Ns - ((i * j * k) - (L * L * L) * Nb);  
23.         if (0 < rest) {  
24.           lli e = i * j;  
25.           k += (rest / e) + (bool)(rest % e);  
26.         }  
27.         mn = min(mn, i * j * k);  
28.       }  
29.     }  
30.     return mn;  
31.   }  
32. };  

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