Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-26

BaseMystery

| 09:14

問題文

n進数を採用したとき、等式を満たすかどうか。見落としが多く、2回システムテストで落とされ、3回目で通った。

class BaseMystery {
public:
    vector <int> getBase(string equation) {
        vector <int> result;
        vector<string> nums(3); 
        nums[0] = string(equation.begin(), 
                find(equation.begin(),equation.end(),'+'));
        nums[1] = string(equation.begin()+nums[0].length()+1, 
            find(equation.begin()+nums[0].length()+1,equation.end(),'='));
        nums[2] = string(equation.begin()+nums[0].length()+nums[1].length()+2,
                equation.end());
        int maxDigit = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums[i].length(); j++) {
                maxDigit = max(maxDigit, getIntDigit(nums[i][j]));
            }
        }
        for (int p = max(2,maxDigit+1); p <= 20; p++) {
            if (toBase10(nums[0],p)+toBase10(nums[1],p)
                                    == toBase10(nums[2],p))
                result.push_back(p);
        }
        return result;
    }
private:
    int getIntDigit(const char c) {
        if (isdigit(c)) return c - '0';
        else return 10 + c - 'A';
    }
    int toBase10(const string& s, const int p) {
        int d = 0;
        for (int i = 0; i < s.length(); i++) {
            d *= p;
            d += getIntDigit(s[i]);
        }
        return d;
    }
};