TopCoder SRM 655 Div2: Med

いらぬ条件を追加して本番は落としてしまった。

問題

WxHの折り紙を与えられる。この紙を折りたたんでいき、折り紙の面積をAにしたい。ただし折りたたむとき、折り目は縦か横の辺に平行でなければならず、折りたたんだ後でも各辺の長さは整数でなければならない。面積Aにするのに必要な折り畳み回数の最小値を答えよ。そのような折りたたみ方がないときは-1を出力せよ。

1 ≦ W, H ≦ 1,000,000,000、1 ≦ A ≦ 100,000

解法

Aの最大値が小さいことに注目する。仮に面積Aを実現できるとして、その一辺を全探索でシミュレートしていき、折り畳み回数を数えていく。その最小値が答えとなる。

一度の折り畳みで縦（横）を半分（辺の長さが奇数のときは少し異なる）まで折りたためるので、できるだけこの折りたたみをしていく。 Aを割り切れるw (1 ≦ w ≦ A)について、h = A/wとする。w ≦ W かつ h ≦ Hのとき、W < 2*wになるまでW = (W+1)/2としていく（Wを折りたたむ）。Hについても同様。計算後、W > ｗならばWを折りたたんでwに、H > ｈならHを折りたたんでをhにしてしまう。

このときの折り畳み回数がA = ｗ*ｈのときに必要な折り畳み回数の最小値となる。あとはすべてのAを割り切るwについて、折り畳み回数の最小値をとれば答えとなる。折り畳みが不可能かどうかはansが初期値のままかどうかで判断すればいい。

def solve(self, W, H, A):
    ans = 10**10
    for w in xrange(1,A+1):
        if A%w == 0:
            h = A/w
            if W >= w and H >= h:
                tmp = 0
                aw,ah = W,H
                while aw >= 2*w:
                    aw = (aw+1)/2
                    tmp += 1
                while ah >= 2*h:
                    ah = (ah+1)/2
                    tmp += 1
                if aw > w: tmp += 1
                if ah > h: tmp += 1
                ans = min(ans, tmp)
    return ans if ans < 10**10 else -1