読者です 読者をやめる 読者になる 読者になる

SRM 655 Div2 Medium FoldingPaper2

問題

SRM 655 - TopCoder Wiki

W,高さHの長方形が与えられる. 今,外周の辺に平行な整数の位置で長方形を折り曲げることが出来る時, 与えられた面積Aにすることが出来る,折り方の最小手数を求める問題.

もし,そのような折り方がなければ-1を返す.

解答

  • 正解の幅はA=w*hとなるような,幅wと高さhなので,まずそのようなwとhを全列挙する
  • w <= Wかつ h <= Hでなければ,可能な折り方は無い
  • Wからw,Hからhを作るような最小手数を求め,そのコストを計算
  • 最小のコストを求める
class FoldingPaper2
{
public:
  vector<int> factors(int x) {
    vector<int> res;
    int i;
    res.push_back(1);
    for (i = 2; i <= x; i++) {
      while (x % i == 0) {
        res.push_back(i);
        x /= i;
      }
    }
    return res;
  }
  int digit (int x) {
    int res = 0;
    while (x > 0) {
      res++;
      x /= 2;
    }
    return res;
  }
  int foldCost(int x, int y) {
    if (x == y) return 0;
    if (x <= 2 * y) return 1;
    return 1 + foldCost(x/2 + x%2, y);
  }
  int solve(int W, int H, int A)
    {
      vector<int> f = factors(A);
      long long inf = (long long)W * H;
      long long res = inf;
      int n = f.size();
      for (int i = 0; i < 1 << n; i++) {
        int w = 1;
        int h = 1;
        for (int j = 0; j < n; j++) if ((i >> j) & 1 ) w *= f[j];
        for (int j = 0; j < n; j++) if (!((i >> j) & 1)) h *= f[j];
        if (w <= W && h <= H) {
          long long cost = foldCost(W, w) + foldCost(H, h);
          // cout << "(w,h)=("<< w << "," << h << ")=" << cost << endl;
          // there is a possible solution
          res = min(res, cost);
        }
      }
      if (res == inf) return -1;
      return res;
    }
};