Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-10

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};