Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-17

Dragons

| 13:52

問題文, SRM 147

餌の奪い合いをした後に、ボスドラゴンはどれぐらいの餌をもっているのかを求める。1回目に出したときは、結果が0になる場合の処理を実装していなかったため、システムテストで落とされた。

150.0/500

typedef long long int64;

class Dragons {
    public:
        string snaug(vector <int> initialFood, int rounds) {
            const static int NUM_SIDES = 6;
            const static bool d[NUM_SIDES][NUM_SIDES] = {
                { false, false,  true,  true,  true,  true },
                { false, false,  true,  true,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true, false, false,  true,  true },
                {  true,  true,  true,  true, false, false },
                {  true,  true,  true,  true, false, false } };
            vector<pair<int64,int64> > food(NUM_SIDES);
            for (int i = 0; i < NUM_SIDES; i++)
                food[i] = make_pair(initialFood[i], 1);

            while (rounds-- > 0) {
                vector<pair<int64,int64> > oneFourth(food);
                for (int i = 0; i < NUM_SIDES; i++) {
                    oneFourth[i].second *= 4;
                    oneFourth[i] = reduction(oneFourth[i]);
                }
                food = vector<pair<int64,int64> >(NUM_SIDES, make_pair(0,1));
                for (int i = 0; i < NUM_SIDES; i++) {
                    for (int j = 0; j < NUM_SIDES; j++) {
                        if (d[i][j]) 
                            food[i] = addFrac(food[i], oneFourth[j]);
                    }
                }
            }

            ostringstream res;
            const static int BOSS = 2;
            if (food[BOSS].first == 0) {
                res << 0;
            } else if (food[BOSS].second == 1) {
                res << food[BOSS].first;
            } else {
                res << food[BOSS].first << "/" << food[BOSS].second;
            }
            return res.str();
        }
    private:
        int64 gcd(int64 c, int64 d) {
            if (c==0 || d==0) return 1;
            int64 v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int64 lcm(int64 c, int64 d) {
            return c / gcd(c,d) * d;
        }
        pair<int64,int64> reduction(const pair<int64,int64> a) {
            int64 g = gcd(a.first, a.second);
            return make_pair(a.first/g, a.second/g);
        }
        pair<int64,int64> addFrac(const pair<int64,int64> a, const pair<int64,int64> b) {
            pair<int64,int64> ret;
            int64 l = lcm(a.second, b.second);
            ret.second = l;
            ret.first = a.first*(l/a.second) + b.first*(l/b.second);
            return reduction(ret);
        }
};

ゲスト



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