Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-02-03

Packhorses

| 06:13

問題文, SRM 179

自力で解けなかった。以下は Editorial で述べられている Brute force な解答。

165.0/550 (cheated)

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int result = INT_MAX;
        for (int i = 0; i <= p; i++) {
            int xx = max(0, x-2*i);
            int yy = max(0, y-(p-i));
            result = min(result, p + (xx+2)/3 + (yy+1)/2);
        }
        return result;
    }
};

それと一定時間で解く方法が以下。最初の if (y%2 != 0) { ... } は、こうしないと (x,y) = (3a, 2b+1) (a,bは任意の自然数)の場合に対応出来ないから必要。

class Packhorses {
public:
    int horses(int p, int x, int y) {
        int rem = p;
        if (y%2 == 1) {
            y--;
            rem--;
        }
        if ((x+1)/2 < rem) {
            rem -= (x+1) / 2;
            x = 0;
            y -= rem;
            y = (y < 0) ? 0 : y;
        } else {
            x -= 2 * rem;
        }
        return p + (x+2)/3 + (y+1)/2;
    }
};

NelleNelle 2011/07/10 03:50 Shoot, who would have touhght that it was that easy?

eucmwztyzkeucmwztyzk 2011/07/10 16:56 z0NxqO <a href="http://hsgtzyqhmovt.com/">hsgtzyqhmovt</a>

wsahgnbbybpwsahgnbbybp 2011/07/11 18:47 rSe9kY , [url=http://eabtqfkuruwb.com/]eabtqfkuruwb[/url], [link=http://uzoqnjdenqul.com/]uzoqnjdenqul[/link], http://eulnzbieqxug.com/

fahoslsfahosls 2011/07/12 18:23 znpKbM <a href="http://lmfoqmdfvcpr.com/">lmfoqmdfvcpr</a>

dspfvndspfvn 2011/07/12 22:56 I7LUvz , [url=http://dqdjjrbohqdj.com/]dqdjjrbohqdj[/url], [link=http://mhsjmpzjdfmi.com/]mhsjmpzjdfmi[/link], http://uyelavyaiohl.com/

IceIce 2013/02/18 17:06 A million thnkas for posting this information.

ezbdugvezbdugv 2013/02/19 02:06 uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv 2013/02/19 02:06 uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

ezbdugvezbdugv 2013/02/19 02:06 uJLKpj <a href="http://gtvcccrcfhuh.com/">gtvcccrcfhuh</a>

qnsmprqnsmpr 2013/02/19 02:06 IDXBp6 <a href="http://tdiutlvrhsqr.com/">tdiutlvrhsqr</a>

ldlhvtldlhvt 2013/02/21 14:11 jqHKkH <a href="http://ihumrmpkwbiu.com/">ihumrmpkwbiu</a>

rexpxqrexpxq 2013/02/21 18:34 FMdzWL , [url=http://fvgkmkrgfoyd.com/]fvgkmkrgfoyd[/url], [link=http://dfkwhpnoefiw.com/]dfkwhpnoefiw[/link], http://elpxctkydvad.com/

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20100203