Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-04

PaperFold

| 18:43

問題文

8回以下の回数だけ紙を折ることで、箱にその紙を納められるか。

class PaperFold {
    public:
        int numFolds(vector <int> paper, vector <int> box) {
            box.push_back(0);
            queue<vector<int> > Q;
            Q.push(box);
            while (!Q.empty()) {
                vector<int> b = Q.front(); Q.pop();
                if (b[2] > 8) continue;
                if (isFit(paper, b)) return b[2];
                b[2]++;
                b[0] *= 2; Q.push(b);
                b[0] /= 2; b[1] *= 2; Q.push(b);
            }
            return -1;
        }
    private:
        bool isFit(const vector<int>& paper, const vector<int>& box) {
            return (paper[0] <= box[0] && paper[1] <= box[1]) ||
                (paper[0] <= box[1] && paper[1] <= box[0]);
        }
};